Skip to main content

Recursion Basics

Getting a hang of Recursion

Let's try to understand this using an example. Let's say, given a number N, we'd like to write code for finding the factorial of N. Of course, there is an iterative way to do so, as can be seen below:

int factorial(int n) {
  int ans = 1;
  for(int i = 1; i <= n; ++i) {
    ans *= i;
  }
  return ans;
}

But what we're interested in is the recursive way to do it.

💡
Whenever thinking about a recursive solution, try to think of a smaller or a different version of the same problem, the answer of which can be used to solve the actual problem.

For example, the actual problem above is to find factorial(n), but if we're able to somehow get the answer to a smaller version i.e. factorial(n-1), then it's fairly easy for us to get the value of factorial(n) using the following formula:

factorial(n) = factorial(n-1) * n

Now, the next step is to ask yourself, that what is the smallest version of the same problem that is independent of any other version and can be answered directly?

Try to think for this case.

Well, for the given example, if N = 0, then you won't find factorial(-1) to get the answer for factorial(0), right? xD

In this case, we simple know, that factorial(0) = 1.

Well, after these 2 steps, it should be fairly easy to convert the thoughts into code.

Implementation 
int factorial(int n) {
  if(!n)
    return 1;
  return factorial(n - 1) * n;
}

How does the code work internally?

Good question.

Internally, there is something called a call stack.

The main purpose of the Call Stack is to keep track of the point to which each active subroutine (or function) should return control when it finishes executing.

In layman terms, the code is getting executed line-by-line in the main() function, and there is a function call factorial(5) on line number 10. Then, there will be a function call added to the top of the call stack, and it will somehow be stored in the structure, that when this function call is done, the code should resume from line number 10. (because the call was made on line number 10)

The diagram above is an attempt to briefly illustrate what's explained.

I hope you're getting a hang of it ✌🏻