Explained with drawings

Photo by Juliana on Unsplash

In the following pictures, we will take an in-depth 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);
}

What you are seeing here is a recursive function, which is a function that calls itself. It has 3 execution stages, set as if statements. The first one returns a value of 1, if our variable Y is equal to 0; the second one is executed if Y is lower than 0, and the third one is executed if Y is neither lower nor equal to 0. For this article’s purpose, we will say our X variable is equal to 5, and our Y variable is equal to 3.

Since Y is neither lower nor equal to 0, our function will call itself over and over, each time deducting a value of 1 to our Y variable. What is interesting is that Y eventually is equal to 0, in which case the if statement set for that case is executed. With the previous image, is easy to visualize what is happening in terms of our function, but what about the stack and how all of this relates?

The stack is a place in memory that stores operations in a LIFO (last in - first out) order. This means that the operations in our function are stored as shown above. Our function is basically counting itself backwards (in our case from 3 to 0), and when it reaches zero, it multiplies X by the number of times it went backwards, which is 3. This is exactly what we do when we need to figure out a number to the power of another number (in our case 5 to the power of 3).

Please be mindful that our function had a kind of “break”, a state that when reached stops the recursion. If our function only had the third case, like this:

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

We would have an infinite loop and what’s called a stack overflow, because our function would be executing itself, and occupying memory, over and over again. Recursive functions are incredibly powerful, but you need to be careful when using them.

Sometimes writer, avid for programming.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store