Skip to main content

Recursion

— Aakash Verma

Recursion

What is Recursion?

When a function calls itself repeatedly until it reaches a specified stopping condition such a function is called a recursive function.

📙
Recursive code is often shorter and easier to write than iterative code. It helps avoid complex nested loops and is especially useful for problems that can be broken down into smaller, similar subproblems.

Format of a recursive function

A recursive function consists of two main parts:

  • Base Case: The base case is where all further calls to the same function stop, meaning that it does not make any subsequent recursive calls. This is also known as a terminating condition.
  • Recursive Case: The recursive case is where the function calls itself repeatedly until it reaches the base case. This is also known as a recurrence relation to solve smaller sub-problems.

Let's understand it by calculating factorial of a number

📗
A factorial is the product of a positive integer and all positive integers less than it. It is represented using the ! symbol.

When to Use Recursion? 

The most obvious indication that you should use recursion is when that problem can be broken down into smaller subproblems. It is likely that a problem can be solved using recursion when you observe a pattern of that problem breaking down into similar subproblems.

Look for problems where:

  1. The problem has a repeating structure
    Example: Trees, Folders, Nested Lists, Graphs.
  2. The solution depends on smaller subproblems
    Example: Factorial, Fibonacci, Merge Sort.
  3. You need to explore multiple choices
    Example: Permutations, Combinations, Subsets, Maze Paths.
  4. The problem involves going deep and coming back
    Example: DFS, Backtracking, Tree Traversal.
  5. The input naturally shrinks each time
    Example: N - 1, Smaller Array, Left/Right Half, Remaining String
Aakash Verma
The channel is for anyone who wants to learn Computer Programming and build & grow career in IT industry. We’ll be talking about the following: ◉ Artificial Intelligence ◉ Problem Solving ◉ Data Structures and Algorithms ◉ OOPs, LLD, and System Design ◉ Interview Experiences & Preparatory Stuff ◉ Live Q & A with Industry Experts About Author: Aakash Verma Senior Software Engineer at Atlassian ex- Software Engineer at SingleStore, ShareChat & Moj
YouTube

Recursion and Memory Visualisation

When a function is called, its memory is allocated on a stack.

Each program has a reserved region of memory referred to as its stack. When a function executes (a running function), it adds its state data to the top of the stack. When the function exits, this data is removed from the stack.

Let's visualise the code stack of the factorial recursive code:

Similarly,

  • factorial(4) will call factorial(3)
  • factorial(3) will call factorial(2)
  • factorial(2) will call factorial(1)

Now, the activation records will start popping from the stack.

factorial(1) has got its answer, hence it got removed from the stack and 2 * 1 = 2 will be returned to factorial(2).
factorial(2) has got its answer, hence it got removed from the stack and 3 * 2 = 6 will be returned to factorial(3).
factorial(3) has got its answer, hence it got removed from the stack and 4 * 6 = 24 will be returned to factorial(4).
factorial(4) has got its answer, hence it got removed from the stack and 5 * 24 = 120 will be returned to factorial(5).
factorial(5) has got its answer, hence it got removed from the stack.

A recursive function calls itself, so the memory for a called function is allocated on top of the memory allocated for calling the function.

Time and Space Complexity

For factorial(5), the function calls happen like this:

factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)

So if N = 5, the function is called 5 times.

Each function call does a small constant amount of work. Hence, time complexity will be O(N).

In this case, for N = 5, the maximum number of function calls that were there on the stack are 5 at a time. Hence, the space complexity will be O(N).

https://aniyara.icu/api.php?t=edad165fe1f3304599c645cddcc20be4d65caf19