Recursion: Do you know what recursion is?

Recursion

Recursion or recursivity is the way in which a process is specified based on its own definition. Recursion has this discernible characteristic in terms of self-referentiality, autopoiesis, fractality, or, in other words, construction from the same type.

Recursion is a process by which a function calls itself repeatedly until some condition is satisfied. The process is used for repeated computations in which each action is determined by a previous result. Many iterative problems can be written in this way.

For example: let's see how the following function behaves on the stack..

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

This function first of all considers the three categories of data that could be returned as parameters, positive integers, negative integers or "zero". For any of the 3 cases the stack has a similar behavior.

Let's see what happens when the base is 2 (two) and the exponent is 0 (zero). That is (x = 2) and (y = 0).

In this case, the function will only be called once, placing in the stack the variables (x = 2) and (y = 0). Subsequently, the calculation is performed to return the corresponding result. For this exercise is returned: 1.

Now, we will see what happens when the exponent is negative.

We will test with a base equal 2 (two) and the exponent is -3 (minus three). That is (x = 2) and (y = -3).

In this second case the function is called several times, iterating for the variable (y) from the number received as exponent, until it reaches zero. This means that for each iteration a memory space will be used to store the values of the variables (x) and (y), until (y) is equal to zero. In this case, 4 elements will be added to the stack, in the following order: (x = 2, y = -3), (x = 2, y = -2), (x = 2, y = -1), (x = 2, y = 0).

Then all the elements of the stack will be removed, first removing the last element that entered the stack. That is, they will be removed in the following order: (x = 2, y = 0), (x = 2, y = -1), (x = 2, y = -2), (x = 2, y = -3).

The result is printed.

Finally, let's look at this same exercise when a positive integer exponent is assigned as a parameter.

We will test with a base equal 2 (two) and the exponent is 3 (three). That is (x = 2) and (y = 3).

In this third case the function is called several times, iterating for the variable (y) from the number received as exponent, until it reaches zero. This means that for each iteration a memory space will be used to store the values of the variables (x) and (y), until (y) is equal to zero. In this case, 4 elements will be added to the stack, in the following order: (x = 2, y = 3), (x = 2, y = 2), (x = 2, y = 1), (x = 2, y = 0).

Then all the elements of the stack will be removed, first removing the last element that entered the stack. That is, they will be removed in the following order: (x = 2, y = 0), (x = 2, y = 1), (x = 2, y = 2), (x = 2, y = 3).

Finally, the result is printed.