What is Recursion? Let’s explore what is happening with visualization

We always think Recursion is nothing but a complex approach. But, recursion itself can be used to create a simple, clean and short solution. Let’s explore the very basic recursion, with an example and some visualization.

Let’s try to solve a common problem:

The squared sum of numbers till N

Ex: for n=3, Sum = 1*1 + 2*2 + 3*3 = 14

To solve this, you could simply use a loop till N and sum up the squared values like below:

Non-recursive way code

Can we use recursion instead of the loop?

Hmm….!! Let’s think………!!

We may have already known that recursion is nothing but calling itself. If it is calling itself indefinitely, there should be a criteria/condition for when the calling chain should be stopped. This condition is named the Base condition.

Let’s try to think in a recursive way like below (for n = 3):

• What is the squared sum till 3?
  3*3 + the result of the squared sum till 2
• Now, what is the squared sum till 2?
  2*2 + the result of the squared sum till 1
• Now, what is the squared sum till 1?
  1*1 + the result of the squared sum till 0
• Now, what is the squared sum till 0?
  It must be 0 (Base condition)

Using the above explanation, result
= 3*3 + (2*2 + (1*1 + (0)))
= 3*3 + (2*2 + (1*1))
= 3*3 + (2*2 + 1)
= 3*3 + 5
= 14

Mathematically we can visualize like below:

sumSquare(3) = 3*3 + sumSquare(2)
sumSquare(2) = 2*2 + sumSquare(1)
sumSquare(1) = 1*1 + sumSquare(0)
sumSquare(0) = 0   <<---Base condition (Stop the recursion)

So, sumSquare(3) = 3*3 + sumSquare(2)
                 = 3*3 + (2*2 + sumSquare(1))
                 = 3*3 + (2*2 + (1*1 + sumSquare(0)))
                 = 3*3 + (2*2 + (1*1 + 0))
                 = 3*3 + (2*2 + 1)
                 = 3*3 + 5
                 = 14

So, the recursion equation will look like this:

sumSquare(n) = n*n + sumSquare(n-1)   when n >= 1
sumSquare(n) = 0                      when n = 0

If you are having a tough time understanding the above explanation, you can skip it, in real world of problem solving you will hardly think about equations. The equations are made to illustrate the theoretical approach.

Let’s do some recursion code

We can see the code snippet below:

Recursive way code

So, for each value of n, we are calculating the square of it by n*n and adding the result of the recursion call with the value n-1. We are keeping this process until n reaches 0.

The visualization of the recursion

The call sequence and the calculation is illustrated below (for n = 3):

Recursion illustration (Zoom to expand the illustration)

Under the hood of Recursion

We can see every time we are calling the function in a recursive way, the previous state of the function is saved until the called function returns. When the base condition is met, the function will not call any recursion which will stop the recursion process. The place where the function state is saved is named Call Stack. We are saying Stack because the function states are saved in the Last Come-First Out (LIFO) manner (see the figure above). The Call Stack is nothing but a position/segment of the memory. So, the space complexity of the recursion process will always be O(N), N = the max recursive calls.

When we don’t use a proper base condition, the recursion process can’t be stopped. As a result, the function states will be pushed into the Call Stack continuously and at some point, it will overflow which is known as Stack Overflow.

Recursion — another way

You may have already a question, why we have started from n and recursed till 0, can’t we use the reverse way, start from 1 till n?

Let’s explore! For the 1 to n approach the recursion example will look like this (for n = 3):

• What is the squared sum from 1 to 3?
  1*1 + the result of the squared sum from 2 to 3
• Now, what is the squared sum from 2 to 3?
  2*2 + the result of the squared sum from 3 to 3
• Now, what is the squared sum from 3 to 3?
  3*3 + the result of the squared sum from 4 to 3
• Now, what is the squared sum from 4 to 3?
  stop and return 0, as we were interested till 3 (Base condition)

The code will look like below:

Recursive way code (another approach)

As we can see, with this approach we have needed two parameters. One for (= s) the current number to be processed and another for (=n) checking the base condition. Both of the programs seem the same except for the base condition. However, both approaches have the same output and space O(n)/time complexity O(n).

Here, we are starting from 1 (bottom), and continued till n (up). That’s why we can call this approach the bottom-up approach.

But, with the previous approach, we have started from n (top) and continued till 0 (down). That’s why we can call the previous approach the top-down approach.

Hopefully, the above illustrations and the example could help you to visualize how recursion works. Thanks for reading!!