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.

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?

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

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 ✌🏻