Recursion: to the end of the stack, and back-

As a programmer, one of the most key attributes you can have is optimization. In programming, this can be put into practice in a wide variety of ways, and the more you incorporate, the better of a progammer you will be.

Some recommended optimization practices include being able to explain an algorithm in as few words as possible and getting it through, whiteboarding clearly and as educationally as possible, and efficient coding that prevents over use of system memory. With small programs, the total run time may not be an issue, but with bigger programs it may become a hassle if the code bulks the system and runs slow — a.k.a is not optimal.

Efficient coding includes numerous practices, but one very noticeable is not abusing loops. A few nested loops is alright, but when there’s one too many, then the optimization radar will probably be ticking. And with what can you replace loops? You got it, with recursion.

And with that, fellow readers, let’s get right into the subject that brought us to this blog.

Recursion

By definition, recursion is:

the repeated application of a recursive procedure or definition.

Funny that in it’s own defintion, recursion uses the word recursion. This alone is a definition of the concept itself and makes it pretty self explanatory. Because put in another way and relating it to programming, recursion refers to a function or procedure that calls itself.

The way this works is a function that within itself, that function is called again.

A recursive function must have at least two conditions for it to work properly:

• A base case
• An interation/increase/decrease

Base Case:

As with loops, recursive functions need a base case also known as an exit condition in order to prevent an infinit loop. Put into practice, this means that the function will be called until that condition is reached. Then it will begin the recursion itself which we will get into in a bit.

Iteration:

Again as with loops, every time a recursive function is called, a change has to happen with at least one of the participating variables so as to get closer to the base case. If there is no change, then an infinite loop will be achieved.

To further explain the concept, there is no better way than to put it into practice. Take a look at the following code:

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

At first glance it looks like a regular short function, yet on a more detailed look, we can see that inside the function, the same function is called again.

This is an example of a recursive function. This function receives two floats, xand yand calculates the result of xto the power of y.

With a loop, this could be resolved in the following way:

int pow(x, y)
{
     int i, result = x;
     for (i = 0; i <= y; i++)
     {
         result  * = 2
     }
     return (result)
}

This is correct, and will only work for positive numbers, unless edge cases are added. Then, another loop should be added in case a number is negative. So to start with, we already have two loops just to calculate a number to the power of another. Seems a bit much huh?

The top solution is much more efficient and therefore preferable. Since recursion is a complex concept yet as important as it may seem complicated, we will break it up into steps and explain what happens backstage to further comprehend the solution and maybe feel more comfortable to put it into practice.

Stack ‘em

To fully understand how recursion works, one must understand the Stack.

A stack refers to an ordered, organized, “pile” of something. Imagine a stack of Legos.

In a system, the stack refers to a data structure where items are placed in an orderly fashion and the address in memory is known at all times because of the organized way they are stored. This system stack is used apart from the heap and stores momentarily information about the subroutines being carried out, until it is their turn to be executed. The “Lego” piece where each subroutine is stored is called a stack frame. Items are “pushed” into the stack, just as you would a stack of Legos, and “popped” out in the same way. The order is LIFO — meaning Last In, First Out. This means that the first item to be stacked, is the last one to be removed. In the same way the last one to be added is the first one to be removed.

This can be illustrated in the following GIF:

The black borders cannot be trespassed, meaning that items can only enter and exit through the opening on the top. Taking this into consideration, we can further comprehend how this system works and it will be of extreme importance in order to understand what is to come.

And what does this have to do with recursion?

Well, everything! Recursion as we said before is a function that calls itself. System wise, this means that another instance of the function is called, while the first one was still running, which means that the first one did not finish executing. Functions will be called within each other over and over until the exit case is reached. When this happens, there will be a lot of “opened” functions waiting to be completed. Every one of these instances or subroutines will be momentarily stored in one of the stack frames. Once it’s their turn to be finished executing, they will leave the stack and it will be the turn of the instance below to be executed, and it continues like that until there are no more subroutines left in the stack, and therefore the program is finished.

Let’s look at that example again:

After looking at the example and understanding how the stack works with recursion, we can now break down the example step by step and understand it.

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

So, what we know:

• It is a function that returns a float, it is called _pow_recursion (hint on what it will do), and it receives two floats, x and y.
• If y equals 0, then the function returns 1.
• If y is less than zero, the function calls itself again with the same x and adding 1 to y. It will continue to do so until the exit case of y = 0, and then go back to every subroutine and divide by x.
• If y is bigger than 0, then the function will call itself again with the same x and substracting 1 to y until the exit case of y = 0 is reached and then go back by multiplying by x for every return value in every subroutine that was saved on the stack.
• The final return value will be the result of x to the power of y.

Let’s focus on a case of two positive values for both x and y.
And what better way to illustrate this function than with another GIF:

Watch it as many times as needed, and refer back to it after the explanation.
We will begin with values x = 2 and y = 6, so this function will calculate the value of 2 to the power of 6.

On the right side at first you will see the code, and the part where the values enter the function will be highlighted in a different color. Every color represents a different stack frame that will be represented on the left side of the GIF, storing the values for each function call in its corresponding color and order. Once the exit case is reached, then the callback with start, each with it’s own color calculating the return values until every stack frame is traversed and the program ends with a final result.

The function enters with the values x = 2 and y = 6 as I said earlier. y is not 0, nor smaller than 0, so the function goes straight to the last return. Before returning, the function is called again, so our first subroutine is stored in the first stack frame. The * x is still pending, but because the function was called, this remaining multiplication is left for the callback of the function.

And like that it will continue, with y = 5, y = 4, y = 3, y = 2 and y = 1, saving a function call in every stack frame as the function is recalled every time. Lastly, when y = 0 the function will not go to the second return but instead reach the exit case and return 1.
And this is when the callback begins, in the LIFO order we saw earlier.

1 is returned to the previous callback, and the * x is still pending from this function call. Because x = 2, the return value will be multiplied by 2 in order to finish that pending part of the function. So that function call, after the multiplication, will return 2 to the previous callback. And will continue like that for every step, always multiplying by 2 since it is the value of x and it never changes. So 2 * 2 = 4, 4 * 2 = 8, 8 * 2 = 16, 16 * 2= 32, 32 * 2 = 64, and since this last one is the final frame of the stack and therefore the last subroutine pending to finish the recursion, the value 64 will be returned and the program will be finalized.

And that *dramatic pause*…. is recursion… *claps and bows*

At first it may seem like a lot and pretty overwhelming to understand, but as with everything in life, practice makes perfect and it is with putting it into practice that one as a programmer can perfect this method and feel more comfortable applying it.

I hope this post and the animated drawing made the comprehension a bit easier. Recursion is defenitely one of the most interesting and useful features of programming and is not only efficient but can also replace almost any loop. Try applying recursion at least one time in a function, and maybe then more than once in the same function…? *mindblown*

Bonus track

Did you know that recursion is not only exclusive to programming? There are numerous examples of recursion in our daily lives as well as in nature. If you come up with any examples leave a comment below!
Happy recursion hunting! :)