Understanding Recursion

What is Recursion?

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. Using recursive algorithm, certain problems can be solved quite easily.

The above function does no useful work as such, but it does demonstrate recursion. The recursive relation above would be

T(N) = T(N - 1) + O(1)

This simply means that the execution for the call to random_function(n) cannot proceed until the call to random_function(n-1) is completed and so on.

Essentially, we delay the execution of the current state of the function until another call to the same function has completed and returned it’s result.

The compiler keeps on saving the state of the function call now and then moves onto the next function call and so on. So, the compiler saves function states onto a stack and uses that for computations and backtracking.

Recursion stack of a set of function calls.

Factorial of a Number

Let us see how we can find out the factorial of a number. Before that, let’s see what the factorial of a number represents and how it is calculated.

factorial(N) = 1 * 2 * 3 * .... * N - 1 * N

Simply put, the factorial of a number is just the product of terms from 1 to the number N multiplied by one another.

We can simply have a for loop from 1 to N and multiply all the terms iteratively and we will have the factorial of the given number.

But, if you look closely, there exists an inherent recursive structure to the factorial of a number.

factorial(N) = N * factorial(N - 1)

It’s like offloading the computation to another function call operating on a smaller version of the original problem. Let’s see how this relation would unfold to verify if the solution here matches the one provided by the for loop.

Showing the steps from top to bottom for the factorial recursive function

Verification that the recursive function defined produces the correct result

So, it is clear from the two figures above that the recursive function that we defined earlier,

factorial(N) = N * factorial(N - 1)

is indeed correct. Have a look at the Python code snippet used to find the factorial of a function, recursively.

This example was pretty simple. Let us consider a slightly bigger but standard example to demonstrate the concept of recursion.

Steps to come up with a Recursive Solution

1. Try and break down the problem into subproblems.

2. Once you have the subproblems figured out, think about what information from the call to the subproblems can you use to solve the task at hand. For example, the factorial of N — 1 to find the factorial of N , height of the left and right subtrees to find the height of the main tree, and so on.

3. Keep calm and trust recursion! Assume that your recursive calls to the subproblems will return the information you need in the most optimal fashion.

4. The final step in this process is actually using information we just got from the subproblems to find the solution to the main problem. Once you have that, you’re ready to code up your recursive solution.

Now that we have all the steps lined up, let’s move on to our final problem in this article. It’s called Sum of Distances in a Tree.

Why Use Recursion?

Recursion is preferred when the problem can be broken down into smaller, repetitive tasks. These are the advantages of using recursion:

1. Complex tasks can be broken down into simpler problems.
2. Code using recursion is usually shorter and more elegant.
3. Sequence generation is cleaner with recursion than with iteration.

But you should not use recursion every time just because it is possible to do so.