Focus on the recursion – part I

Recursion is very commonly used in computer science, and can be a little hard to understand at first. Let’s try to review what recursion is, and how it works, with some examples.

Basically, in computer science, recursion is a kind of algorithm where the main task can be divided into same and repetitive sub tasks.
A nice analogy (which I got inspired from here) says like that: Let’s pretend that you’re standing in the last place of a long checkout line of a drugstore. Now, you really want to know the number of persons waiting their turn in front of you. You’re too lazy to count so you ask Mike who is standing in front of you to tell you how many people are there in front of him. Mike does the same thing and asks Patil who is standing in front of him and so on till Alice who is standing first is asked the question. Alice can answer Jack standing in the second place because she can see that there are no more people in front of her. This is the base case (or later in this article: stop condition). Jack adds 1 to Alice’s answer and tells it to Jill who is in the third place and so on until the answer reaches you. Notice that at each step the problem is reduced to a simpler version of the same problem.

A lot of problems can be easily solved with help of recursion, where iterations would have turned to be way more difficult to think.
Still, it does not mean you should use recursion with no hesitation. It can easily cause stack overflow, if the number of recursive calls is too big. But this is not our subject!

Let’s see now an other question, which can be solved with recursion:
A ladder has n steps, one can climb the ladder using any combination of steps of 1 or steps of 2. How many possible ways are there for one to climb the ladder? For example, if the ladder had 3 steps, these would be the following possible paths: 1-1-1, 2-1, or 1-2.

How to tackle such problem? The answer is IMHO, always the same: trying with simple examples to get to a pattern.
And here, it seems that if I know how to solve the problem with 3 steps – let us call the result L(3), I will know how to solve it with 4. Why ?
Because I have only two possibilities: 1) start with climbing 1 step and then the 3 remaining have L(3) possibilities, or 2) start with climbing 2 steps and then the 2 remaining have L(2) possibilities (remember the question, I can climb only by steps of 1 or 2).
Then L(4) = L(3) + L(2).
Again for 5 steps:
Two possibilities: 1) start with climbing 1 step and then the 4 remaining have L(4) possibilities, or 2) start with climbing 2 steps and then the 3 remaining have L(3) possibilities.
Then L(5) = L(4) + L(3).

You got it? Did you recognize it? Well played, we are here in presence of a Fibonacci sequence. Which is defined as follow:
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)
To determine next element, you simply add the two previous ones.
F(2) =F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
etc….

To write a recursive code, what you need first is to identify what your stop condition is, which is the condition which will stop the recursive loop. In our ladder question, it is obviously n = 1 and n = 0, which respectively return 1 and 0. (I need here 2 stop conditions because every new term to be calculate needs to know the 2 previous terms and sum them up)
Then you need to identify the recursion pattern, i.e what each step of the recursion should ask next level to do. Here F(n) = F(n-1) + F(n-2), until we get to n = 1.

See following code:

unsigned int fibo(unsigned int n)
{
  /* Stop condition */
  if (n == 0 || n == 1) {
    return n;
  }
  /* Recursive call */
  return fibo(n - 1) + fibo(n - 2);
}

See how we start from the stop condition:

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

which will allow the recursive loop to stop as soon as we calculate fibo(2) = fibo(1) + fibo(0) = 1 + 0 = 1.

Then we have the pattern:

return fibo(n - 1) + fibo(n - 2);

For n = 3: fibo(3) = fibo(2) + fibo (1) = fibo(1) + fibo (0) + 1 = 1 + 0 + 1 = 2.
Simple right?

What is extraordinary in recursion, is that when you managed to think in terms of: “let’s say I have result for one level below, I know how to use it to compute next level” (exactly like the one standing last in the row tells himself: “if only someone could tell me how many people are in front of me, I’d surely know what is my position, by simply adding one), then you got it all.

I hope this article helped you to understand basic recursion a little bit more. This is only an introduction for another more complex and interesting question I will treat in next post. Keep on touch!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s