Recursive Recurring Recursion

Oh no, here we go again. It seems like recursion is a topic where you first must understand recursion to understand recursion. Jokes aside, we have all encountered recursion at some point. For some people, it was crystal clear to understand, for others, not so much. When I was first introduced to recursion in high school, I was told the same as most others:

1. Find the base case
2. Recursive Step
3. Trust your code

It appeared as if teaching to trace recursion and discussing about the role of the call stack was primarily disregarded. These same steps were repeated in university, and I was confused because I did not have a good understanding of how the computer reads recursive code. Nevertheless, this seemed like a perfect learning opportunity, and no method of learning is better than trying to explain the concept to someone else!

Let's start by taking a random function f(N), and let this function have a recursive call in it. In python, we have a separate call stack on the side that tracks each call to this function. Afterwards, the function will break down into smaller sub-problems, until the problem cannot be broken down anymore. During this process, each call to the function is pushed into the call stack. 

Once the broken down function has reached the base case, each function call is popped from the call stack until the size of the stack is zero. Each time a function call is popped, its result is obtained  with the information from all the previous function calls. Lastly, when there are no function calls left in the call stack, the function returns the result of the last function call in the call stack.

Sounds confusing, right? Let's take a look at a popular example, the factorial of a number. Now, constructing the code is easy. It looks something like this.

Again, let us take the function factorial(N), as well as a call stack. factorial(N)will break the problem down to smaller function calls, and these function calls will be pushed in the call stack. This is done until a function call has reached the base case.

Going back to our call stack, we now pop each item from the stack, and storing the output alongside it. The item on top of the stack will always be the base case. Furthermore, this value is stored, and then we pop the next item in the stack. This is now f(n + 1) or f(2) in this case, which is equivalent to 2 * f(1). Since we already know that f(1) = 1, we now have enough information to solve f(2) = 2 * f(1) = 2 * 1 = 2. Now it is know what f(1) and f(2) is. With this information, we can now solve 
f(3) = 3 * f(2) = 3 * 2 * f(1) = 3*2*1 = 6. This repeating process can be done all the way to the original problem f(N), which will produce the answer. Let's take f(5) as an example, then the recursion will be as follows.

In summary, the answer is always returned by smaller sub-problems. Having a good understanding of the importance of the call stack, as well as the breaking down of problems, is crucial for a better understanding in tracing recursion.

With this understanding in mind, it is easy to see how the computer looks at recursive functions. It is just as easy as explaining to a 5 year old how recursion works! Just explain to a person one year younger than you, and let them explain to a person one year younger then them. Continue this process until you have a 6 year old explaining to a 5 year old! 

That's it for me today, i'll see you in a couple of weeks! Bye-Bye!