Pramithas's blog
Intuitive introduction to Recursion:

Intuitive introduction to Recursion:

pramithas dhakal's photo
pramithas dhakal
·

4 min read

Recursion is one of the topics in CS that puzzles beginners and experienced programmers alike. And it is one of the most important topics while learning data structures and algorithms.

In this article, I will explain recursion intuitively with real-life examples that hopefully will help you understand recursion better.

Somewhere in the internet, I saw an intuitive example of recursion. Let me present it here.

Let's say we are inside a movie theatre. And the person sitting on the last row wants to know how many rows of seats there are. For simplicity, lets assume that the theater is too big for the person to count using his eyes.

To solve this problem, he devises a nice trick. He asks the person sitting before him for the seat number, and the person in turn asks the person before him. This keeps on going until the question reaches to the person sitting on the first row. And this person, as a matter of fact, knows in which row number he is i.e. 1st row. So, he tells that to the person sitting behind him. The person sitting behind him adds 1 to it and tells 2 to the person behind him since he has to include his row. It goes on until the person in the last row that originated the question gets the answer.

This is the intuitive example of how recursion works.

Here are few interesting things to notice:

  1. Every person in each row is doing the same thing, i.e. asking the person before him about the number of seats and telling the answer he gets to the person behind him. Except the first and the last person.

  2. The first person does not need to propagate his answer to the row behind him because the row does not exists. He is the initiator of the recursive call.

  3. The last person does not need to ask the person before him because there is no one sitting before him and that's why he knows he is sitting on the first row.

Now, how to represent the above example in code?

Let's say there are 500 rows. It means the person sitting in 500th row will ask the person on 499th row, person on 499th will ask person sitting on 498th row, add 1 to it and give the result to the 500th row. And, the person on 498th row will ask person on 497th row and so on. It this manner it goes on and on until the first person is reached in which case, he will just return 1.

Without recursion, we can achieve it in this manner:

int call500Row(){
    return call499Row() + 1;
}

int call499Row(){
    return call498Row() + 1;
}

int call498Row(){
    return call497Row() + 1;
}

......................
......................

int call1Row(){
    return 1;
}

Basically, we are have one method defined for each row, and the method for each row calls next row's method. This goes on an on until the method corresponding to the first row is called. The last method just returns 1.

It is evident that all the methods are doing the same thing i.e. calling method for the next row, adding 1 to the return value and returning the result. So, instead of defining method for each row, we can reuse the same method. But, now we will have to pass the row number as the method parameter in order to know in which row we are in. We achieve this by making the function call itself instead of another function. And, the process of function calling itself is called recursion. Let's see how it looks like in code.

int callRow(int n){
    return callRow(n-1) + 1;
}

What was achieved using multiple methods calls above is achieved by this single method here.

But, how do we handle the special case, i.e. the case handled by the last method that just returned 1 ?

We achieve it by adding an if condition, which is called the base condition.

int callRow(int n){ 

    if(n == 1){
        return 1;
    }

    return callRow(n-1) + 1;
}

When the base condition occurs, the method can no longer call itself to get the desired answer. Instead, it should take the responsibility for itself to return the result. In the above method, base condition occurs when n == 1. Here, the callRow() method does not call itself but return the value 1.

This was the intuitive introduction to recursion. In the future articles, we will discuss recursion with more technical details and solve problems so that we can cement our understanding.

RecursionDSAalgorithms