A dream of recursion.

In order to unfold the concept of recursion in an approachable way, let’s start by clarifying two concepts that need to be really clear before moving any forward: stack and heap.

What is stack?

Stack is a special area of the computer memory which stores temporary variables created by a function. Is stack, variables are declared, stored and initialized during runtime. It is a temporary storage memory. When the task is complete, the memory of the variable will be erased.

What is heap?

The heap is the actual memory space available for the computer’s CPU to use. It is restricted only by the actual physical limits of the computer you are working on.

Ok, and then, what is recursion?

Let’s make use of our good old mate Wikipedia:

“In computer science, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. Recursion solves such recursive problems by using functions that call themselves from within their own code.”

And that is the key, a recursive function is a function that calls itself.

In order to further explain the concept, let’s use an example of a recursive function that calculates a number (x) taken to the power of a second variable (y).

float _pow_recursion(float x, float y)
{
    if (y == 0)
        return (1);
    if (y < 0)
        return (_pow_recursion(x, y + 1) / x);

    return (_pow_recursion(x, y - 1) * x);
}

For the purpose of this explanation, we will be calling the functions using 2 and 3 as x and y.

_pow_recursion(2, 3).

Let’s imagine four little girls playing throw and catch in a single row. Each girl will pass the ball to the next child down the row. Once the ball reaches the last girl, she passes it back to the girl from whom she received the ball. The ball then reverses all the way back to the beginning of the row up to the first girl again (hey, nobody said it was a fun game).

Forcing an analogy, we can think of the garden (or whatever surface these girls are using for their game) as the heap. This is the entire space available for the game to happen.

Again, forcing an analogy, when we call _pow_recursion(2, 3) the row of girls can be pictured like this:

The ball starts with the girl at the far left of the row and represents the variables passed over to the function: x = 2 and y = 3.

That first girl represents the instantiation of a new process with a stack storing the values of x and y.

Each time a girl passes the ball to the next girl at her right, we will imagine that we are calling again to the function, meaning, the instantiation of a new stack on the heap. Once a girl has received the ball and passed it over to the next, only then we could say that a process has finished and its corresponding stack has been cleared.

Now, this are complying girls. They have been instructed to carry on with the game until they are instructed otherwise and they mean to carry on their orders. As we wouldn’t really like to see them faint in exhaustion we better pass them an specific situation that, when met, it will mean to stop keep passing the ball again and again. As we are actually talking about a recursive function, this condition that would end the process is what we call the base case. Whenever the base case scenario presents itself, the recursive function will stop calling itself over. In the _pow_recursion function we are working with, the base case is represented by the first conditional (if):

if (y == 0)
 return (1)

On our scenario the base case represents the point at which the ball has reached the end of the row, all the way down to the last girl, and is backtracked.

Back to the girls playing in the garden, the starting point of the ball is in the hands of the girl at the far left. At this point the ball represents the variables ‘x’ and ‘y’ with the values 2 and 3 respectively. Which means that the base case scenario is not being met as y is not 0 and the ball is not at the end of the row. Therefore, the ball passes to the next girl.

Again, passing the ball to the next girl at the right is an analogy to calling the function again. Even before the first girl has thrown the ball, she has specified the variables it will pass. In our function, this corresponds to the next conditional (the second 'if’):

if (y < 0)
    return (_pow_recursion(x, y + 1) / x);return (_pow_recursion(x, y - 1) * x);

When the ball reaches the second girl, the function calls itself again, but, this new call will receive different parameters than previously. This is actually essential as, otherwise, if the parameters wouldn’t change, a base case would never be met and our girls would pass the ball over and over for all eternity.

When the ball is still at the hands of the first girl, ‘y’ is equal to 3. As 3 is greater than 0, the girl subtracts 1 from ‘y’ and passes the ball to the next girl. This calls the function again but in this case with the updated value of ‘y’ equals to 2, therefore: _pow_recursion(2, 2).

The process repeats itself for the second girl. As ‘y’ is still different than 0 and the ball has not yet reached the end of the row, the second girls substracts 1 to ‘y’ and passes over the ball to the third girl who will then call _pow_recursion(2, 1).

The ball reaches the third girl. The same process for player 3 is instantiated with a stack with the variables ‘x’ = 2 and 'y’ = 1. Again 'y’ is not 0, so the third girl substract 1 from it and pass the ball to the right

When the ball reaches the fourth girl, the base case is met (finally). The ball is at the end of the row and ‘y’ is now equal to 0.

Let’s remember:

if (y == 0)
 return (1);

Having reached the end of the row, the fourth girl sends the ball back from where it came, now representing the return value 1. A fourth process started when the fourth girl received the ball, but immediately terminates and clears after returning the baseball back the other way.

The ball, now representing 1, is received for a second time by the third girl. Let’s remember the expression within which the third girl 3 threw the ball the first time:

return (_pow_recursion(x, y — 1) * x);

Once she receives 1 from the previous girl, the third girl is ready to terminate. She multiplies the received value by its known x (still accessible within her stack) and keep the game going, throwing the ball back with a return value of 2. The third girl has now thrown the ball in both directions, so her process terminates and stack clears.

The second girl receives the ball for the second time and goes through the same process. She multiples the 2 by their known x (2), and send it to the left again, now with the return value 4. The second girl stack is now cleared.

Finally, the ball gets back to the hands of the first girl. It now has gone the entire length of the game row forth and back. The first girl receives the value 4, multiplies it by its known x (2), and returns the final result 8. The first girl’s stack is cleared, and the entire process is over. The girls can now play something else (hopefully funnier), and the garden where they were playing (heap) can be used for something else.

Wrapping up:

While the example we used here was quite simple, the core concept could be applied to much more complicated functions and would still be valid. A recursive function WILL continue to call itself until a base case is met. This lead us to the evident conclusion that we should be really careful about memory usage when implementing recursive functions, as if the base case is not met, the function will keep keep calling itself causing what is known as stack overflow (which is also the name of probably the favorite website for all programmers in the world). When this happens, our computer, which ultimately has physical boundaries regarding the amount of information it can process, will eventually crash and the process will terminate without returning the expected result.

For further clarity here’s the flowchart to the function we used in this article: