Recursion — The best way to simplify some problems

Example of recursive function that calculates the factorial of a number

The sense of recursion will make several processes that in simple code become less difficult to write, so we will explain here its meaning, importance and how to use it when necessary.

What is Recursion

The process in which a function calls itself directly or indirectly is called.

It is the recursive process, a similar iteration is carried out as when you use a For, While loop, the difference is that it does not do it according to values ​​stored in variables, but in the number of times it calls itself, these calls remain stored in memory as a stack.

As in the loop statements, there must be a condition to exit and not continue iterating, otherwise frames will be created infinitely or even cause an error because the memory stack cannot save the recursive function more times, this condition It may be before or after the declaration of the function, which must be fulfilled at some point. The latter is achieved by changing the value that each function call receives.

The Stack Memory

There is something to keep in mind, is that each iteration of our recursive function is stored in the stack, fulfilling the rule of LIFO (last in first out).

The stack allows to store arguments and local variables during the execution of the functions in which they are defined.

Then each time the recursive function is called, this frame is stored, the next frame above it and so on, until reaching a point where each frame ends and returns to the previous one until returning to the first time the recursive function was executed.

As the recursion frames come out one by one, the stack frees space in memory corresponding to each function definition with its respective stored variables. Therefore the stack uses the RAM

Applying the recursion

We are going to carry out an example with a function that allows us to calculate the power by giving the number and the exponent, where the Main function will allow us to print the result:

We see that there are two if statements and a return statement when don´t apply the previous ifs, the first one tells us that it is when “y” is equal to zero then return 1, since there is a mathematical law where every number with an exponent equal to zero, the second valid if it is an exponent is less than zero, that means that it is a negative exponent, it will return the result of exponent plus 1, all this divided by the result of x and the last one when the exponent is a positive number, then returns the result of exponent minus 1, all this multiplied by the result of x.

With a short number and positive exponent:

The steps and in turn the number of frames in the stack will depend on the size of the exponent, in this case we have a number 2 and an exponent 3, we will see how many frames can be stored 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);
}

For in this specific case, 4 frames of the recursive function have been created until reaching when y is equal to zero, then it begins to return and each one will be deleted until reaching the main function.

As a conclusion to this case, as many frames will be created according to the steps that it takes for the value of the exponent “y” to be equal to zero, either from positive or negative numbers, so it would be good to test it not with exaggeratedly large or exaggerated numbers little ones.

Is it worth using recursion?

As this depends on how much memory the stack can contain, it is not recommended in processes where there may be thousands or even millions of frames of a recursive function, because each frame can store the function with defined variables, as it could affect the performance of your machine.

But for processes where the logic can be simplified in fewer lines of code compared to what you would use with loop statements and are not of gigantic volumes, recursion is the best way.

The human mind is normally not used to seeing solutions recursively, however in the software world there are occasions where this is the only way to accurately solve a requirement, it would be good to study basic ways of using it, such as finding the series Fibonacci, the factorial of a number, and then go on to understand the bases of certain algorithm design principles, such as “divide and conquer”, “backtracking”, “dynamic programming” and finally, everything is a matter of practice.

We will see you in a next post.