The recursion in an image
I think that all of us who have ever programmed have come across a recursive function. This is often a confusing topic to understand if you don’t understand how the stack works in a recursive function and the parts required for a function to be called recursively. Therefore, I consider that before presenting an image that can describe recursion, I think it is necessary to put these issues on the table. First of all, let’s define what a recursive function is. This can be defined as a function that calls itself and needs a base case to terminate the recursion.
For example, this is a recursive function:
This function has everything necessary to be a recursive function. As you see on line 8, this function calls itself within it. And also, it has a base case (lines 2 to 4). With just that, the function can now be called recursively.
However, if it were that simple, you wouldn’t be reading this. We know that recursion can usually get very complex depending on what you want. To understand it more clearly, we have to see it from the stack. To do this, we will use this recursive function that calculates the power of a number:
First, we need to identify the base case, which is lines 2 and 3. Then, we’ll start to see how the recursion behaves on the stack:
Each recursive call is saved on the stack and the first call that comes in is the last to be executed. And this can be seen in the Call Stack unpilling:
Having this clearer now we can see the recursion path:
As we saw in the function, each new recursive call decreases exp (the exponent) by one. This is called until exp is 1. Once this is true, it returns each value returned by that function to the previous function call.
Having explained the concepts that I think are necessary to understand recursion, I can show you the best image, in my opinion, that describes how a recursive function works.
But, before that I would like to show you the following image:
With this image, you could imagine taking a single jump on a trampoline and coming out with the same jump. This hypothetical case obtained from the image represents a normal function. The entrance to the trampoline is the beginning of the function. The jump it takes are the instructions that are executed in the function, and the exit of the springboard represents the end of the function.
Now, let me present to you the best representation, that I think can be given, of a recursive function:
With this new image, which looks a bit like the previous one, we can imagine a hypothetical case in which it is no longer taking a jump, but infinite jumps, since it has infinite energy. However, there suddenly comes a point where he gets bored and decides to go play video games. Now let’s do comparisons of each part of the case and how it represents a part of a recursive function. The first entry to the trampoline is the start of the function, each jump it takes is a call to the function recursively, and the decision it makes to go play video games is the base case. Since it had infinite energy, it could have been making infinite jumps (in other words, infinite executions of our function). And that’s exactly what happens when we don’t put a base case, our function runs infinitely many times until our computer runs out of memory.
