Getting Started

Intuition

What if we ask google?

No doubt, it gives us a reasonable answer. But also plays with us by writing "Did you mean: recursion" which is basically an infinite loop xD

But what exactly is it?

Imagine sleeping and having a dream, pretty normal, right? Now, imagine having a dream inside a dream inside a dream inside a dream. Pretty dreamy, right?

Proper Introduction

Well, if we try to write a codified version of it, it'll look something like this:

void dream() {
  dream();
}

If you notice, there is a function dream(), and in the body of dream(), we're calling the same function only i.e. dream(), pretty weird, right?

Well, some may call it weird, some may call it magical, but this is exactly what recursion is.

Making sense of it

Let's make a small change by adding a print statement and try to understand what happens when we run the code.

void dream() {
  cout << "Dreaming\n";
  dream();
}

Now, when this dream() function is called, what will happen is that because of the first line, Dreaming will be printing on the console, then as soon as the control reaches 2nd line, it'll call the dream() function again, then again when we read the dream() function, it'll again print Dreaming according to the 1st line, and then this goes on and on and on....

As you might be able to identify, it'll be stuck in an infinite loop of calling itself again & again & again.

Coming out of the infinite loop

Let's look at a slightly altered version of the above code. Click here to try it on compiler.

void dream(int time) {
  if(time > 8) {
    cout << "Woke up at " << time << '\n';
    return;
  }
  cout << "Dreaming at " << time << '\n';
  dream(time+1);
}

Now, let's say dream(5) is called from the main() function:

1. In the 1st call, "Dreaming at 5" will be printed, and a recursive call of dream(6) will be made.
2. In the 2nd call, "Dreaming at 6" will be printed, and a recursive call of dream(7) will be made.
3. In the 3rd call, "Dreaming at 7" will be printed, and a recursive call of dream(8) will be made.
4. In the 4th call, "Dreaming at 8" will be printed, and a recursive call of dream(9) will be made.
5. In the 5th and the final call, we'll enter the if condition - "Woke up at 9" will be printed, and the loop of the recursive calls will finally end.

Dreaming at 5
Dreaming at 6
Dreaming at 7
Dreaming at 8
Woke up at 9

Remember the part of code in the above example which had that if condition and the recursion stopped on the basis of that part? That part of code is generally referred to as Base Case.

To understand recursion, one must first understand recursion.