Recursion

Memory management

Recursion is a handy tool in daily programming life. Machines can do a good job keeping account of the data while being transformed by a function.

You can think of recursion as a production line in a company where every step will always be the same.
Imagine you have a bold piece of iron and, you need a slim side in your bar. The bar gets inside the production line and receives a strong hammer punch in the first step. Then, measure the thickness of the end of the bar and evaluate if it has reached the desired width. If done, the piece can return. Otherwise, it will receive a new strong hammer punch in the line.

As you can see, the function is the hammer punch and will always be the same. But as the initial conditions of the material have changed, also the partial result will.

How does that work in computers and, how does it work in memory?

Let’s analyze the following 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);
}

Data properties can’t be physically changed but just represented, so the program keeps track of how those properties change after every function run.

The first line of the code indicates that we will receive two arguments of float type. It also tells us how we can call the function.

float _pow_recursion(float x, float y)

Then we find a condition that states: if y equals zero then, return 1.

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

That’s because, in maths, any number powered by zero equals 1. we know that the value entered in var y is the exponential factor so, we can be safe on this. If the code reaches this point, the recursion is over.

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

The following lines state that if y is minor than zero, then execute using the value of x as it is and that y will be y plus one. The result of that operation is then divided by x. That will allow getting powers of numbers raised to a negative number as if it were positive. The recursion will be running if the code reaches this point. The recursion will end when y reaches zero.

Bear in mind that:

• We know that any number raised to the power of one will be the same number.
• We also understand that any number divided by itself will be one.

Finally we got the following lines:

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

The recursion will be running if the code reaches this point.
The function will be calling itself, again and again, each time. Notice how the value of y will be decreased by one each time. That will allow our function to go out of the loop at some point.

The code will bring the value of the exponent to zero, no matter if it’s positive or negative.

In memory, the first function call allocates some space to maintain the value of variable y. The subsequent recursion call grabs new space in memory on top of the previous call until it reaches the exit condition.

Bear in mind that you can create a recursion function that never ends that will consume all of your available memory and crash your computer.

In this case, if you set the value of y with a decimal part like 2.3, that will cause a segmentation fault.