Recursion Explained With Drawings 🎨

Because an image is worth 1000 words, let’s go over what recursion is, how it works and how it is handled by the stack.

Recursion

The definition of recursion is very straight forward:

A recursive function is a function that calls itself.

Here is an example:

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);
}

Simply put, this function calls itself to find the x to the power of y with the following logic:

Let’s see for example what happens if we do: _pow_recursion(5, 3) :

As we can see, here y acts as a counter and each time the function calls itself, its value is reduced by one. That way we can go 4 iterations deep before returning 1 and then multiply this value by 4 until it reaches the 1st iteration, thus doing 5³ .

Recursion and the stack

In this example, we saw the function depends on the previous invocation of itself in order to return the final result. This is what we call: the call stack (or execution stack).

The call stack operates on a “Last In, First Out” (LIFO) basis. An item is “pushed” onto a stack to add to it, and an item is “popped” off the stack when removed from it (when that function returns a value).

So this is how the computer handles the memory during recursion:

Awesome isn’t it?! Doesn’t that remind you of something?