Let’s understand recursion…

…but first! We must understand recursion.

As programs become bigger it also becomes more and more important to make your code efficient. That is why having lots and lots of nested loops might be less than ideal. Here is where recursion might come in handy. So, what is recursion? It is the process in which a function calls itself directly or indirectly. Additionally, a recursive function has two basic requirements: an exit condition and an iteration.

The exit condition, also known as base case, is required in order to prevent an infinite loop since it states that the function will be called until that condition is reached. After that, recursion will take place.

Same as with loops, every time a recursive function is called one or more of the variables undergoes a change and gets closer to the exit condition. Let’s exemplify this with a bit of 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);

}

As you can see the function takes two floats and calculates x to the power of y by calling itself. Alternatively, you could have done this with a loop,

int pow(x, y)

{

int i, result = x;

for (i = 0; i <= y; i++)

{

result * = 2

}

return (result)

}

And then you realize this only works with positive numbers…so you would need another loop for negative numbers. This might not seem like two much for such a simple function but for a bigger program you might end up with a hell of Matryoshka doll looking code. In order to avoid that, recursion is an elegant yet somewhat counter intuitive solution.

The easiest way to understand recursion is to think of the stack, think of a stack of plates for instance. It is an orderly pile of plates and you need to remove the one at the top in order to continue removing the ones below. Likewise, in programming, a stack is an organized data structure and it stores temporary information about subroutines being run. Each subroutine is stored in a “plate” called stack frame. These frames are pushed into the stack and “popped out” in the same way. This is known as LIFO, as in Last In First Out. That way, the last one to be added is the last one to be removed.

This will help us visualize recursion since the function calls itself while another instance of the function is still running, and that instance will call itself again and so on until the exit condition is reached. At this point there will be many running instances of the function waiting to be executed. Meanwhile, these instances are stored in stack frames. At execution they will leave the stack and the next instance will be executed. This will take place until there are no more instances left to be executed.

Now let’s take a fresh look at our function.

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

}

• If y == the function will return 0, what a surprise.
• If y is a negative number the function will call itself adding 1 to y until y == 0, then it will go back to every subroutine and divide it by x.
• If y is a positive number the function will call itself and subtract 1 to y until it reaches the exit condition, then it will multiply it by x in every subroutine.
• Finally, the return value will be the result of x to the power of y.

Let’s illustrate this with two positive values, x = 2 and y = 5.

Since y is positive we go straight to the last return but before the function calls itself thus storing our first subroutine in the stack. However, *x did not take place yet, it will occur when the function is called back. This process will take place for y = 4, y = 3, y = 2, y = 1. When y = 0 we will have reached the exit case and return 1. At this time the callback takes place in LIFO order. 1 is returned to the pending *x. x = 2 so the return value will be multiplied by 2. This subroutube will return 2 and continue in this way for every step until it returns 32 and the program is finalized.

This might seem a bit too foreign at first but Rome wasn’t built in a day so don’t worry if it seems a bit overwhelming at first. I hope this satisfies your curiosity!