Recursion in programming? Recursion in programming? Recursion in programming? ...

The objective of this article is to explain the concept of recursion in programming to people who are just learning the term and are not very clear about its usefulness or the key aspects to take into account.

Therefore… What is recursion? In essence, recursion is a function that calls itself to avoid the use of loops and other types of iterators, which allows you to solve certain problems in a more elegant and efficient way in terms of code.

What characteristics or aspects should be taken into account with recursion:

1. The base condition: It is essential to establish clearly and precisely what is the condition that makes the recursion stop and not continue calling itself indefinitely.
2. The stack: Whenever a function is called from another function, even if it is itself, a new entry is generated in the stack memory, which has a limited space. Therefore, if a recursive function calls itself many times, a stack overflow is possible.

To internalize the concept, I am going to do an example with a recursive function that returns the result of a number raised to any power “n”. This means, in mathematical terms, for example, that 2 to the power of 5 is equal to 2x2x2x2x2, which turns out to be equal to 32. That is, the base, in this case 2, multiplies itself the number of times which indicates the exponent or power, in this case 5 times.

To reinforce the ideas I've expressed above, I'm going to break down the following 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);
}        

Step by step detail:

1. This function receives two floats, “x” and “y”, and returns a float at the end.
2. The exit condition is defined as if (y == 0), return 1. End of the process.
3. If "y" is less than 0, return the recursive function, increasing the value of "y" by 1 and dividing by "x".
4. Otherwise, if no if condition enters, return the recursive function, decrementing the value of "y" by 1 and multiplying by "x".

Functional case:

If we call the function as in the example, where x = 2 and y = 5, the function would basically do the following:

1. Create an entry on the stack when x = 2 and y = 5
2. Create an entry on the stack when x = 2 and y = 4
3. Create an entry on the stack when x = 2 and y = 3
4. Create an entry on the stack when x = 2 and y = 2
5. Create an entry on the stack when x = 2 and y = 1
6. Create an entry on the stack when x = 2 and y = 0
7. Now, since y == 0, the exit condition works and the recursion ends. Therefore, it begins to unmount the entries from the stack.
8. Returns the stack input when x = 2 and y = 0 (Exit Condition)
9. Returns the stack input when x = 2 and y = 1 (which returns 1 * 2 = 2)
10. Returns the stack input when x = 2 and y = 2 (which returns 2 * 2 = 4)
11. Returns the stack input when x = 2 and y = 3 (which returns 4 * 2 = 8)
12. Returns the stack input when x = 2 and y = 4 (which returns 8 * 2 = 16)
13. Returns the stack input when x = 2 and y = 5 (which returns 16 * 2 = 32)
14. Finishes the entire function, with a return of 32.

Non-functional case:

Since this function receives and returns floats, but with each recursion the value of "y" is reduced by 1, then with any float that is not an integer, the exit condition y == 0 will never be met, and therefore , the function will call itself indefinitely, generating a stack overflow.

If we call the function with x = 2 and y = 0.5, the function would basically do the following:

1. Create an entry on the stack when x = 2 and y = 0.5 (y - 1)
2. Create an entry on the stack when x = 2 and y = -0.5 (y + 1, because y < 0)
3. Create an entry on the stack when x = 2 and y = 0.5 (y - 1)
4. Create an entry on the stack when x = 2 and y = -0.5 (y + 1, because y < 0)
5. Create an entry on the stack when x = 2 and y = 0.5 (y - 1)
6. Create an entry on the stack when x = 2 and y = -0.5 (y + 1, because y < 0)
7. And so on, indefinitely until the stack overflows, generating a segmentation fault.

I hope then with this example it has become clear what recursion is and its two main elements to consider: The base condition and the stack. The above concepts are key to ensuring that recursion is successful.

Sources:

https://www.campusmvp.es/recursos/post/Que-es-la-recursividad-o-recursion-Un-ejemplo-con-JavaScript.aspx

https://www.smartick.es/blog/matematicas/recursos-didacticos/las-potencias/