What does recursion mean?

Recursion is a concept used in programming which refers to a process that runs itself a certain number of times until it can solve a particular problem.

To solve a problem with recursion we need to define a “base case” as the solution to that problem, and then define the rules that the process must follow for more complex cases through calls to itself. What we want to achieve with this way of doing things is to progressively reduce the complexity of the problem to be solved until the last process executes the previously defined base case. Otherwise, the recursive process will run infinitely.

To execute a recursive algorithm, what the operating system does is to allocate new memory on the call stack for the new call to the function itself. Then, this new function will allocate more memory for the next function call, and so on until it reaches the base case, whose memory will be the first to be freed after finishing its execution. After that, the remaining methods of the next call on the stack are executed, until it is finished and its memory is freed to continue the process with the next call below… until returning to the main case, which will finally obtain the expected result.

Let’s see an example of this (in C). We define _pow_recursion as a function that powers x to the exponent y .

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

Let x = 3 and y = 4. This function could be represented in the call stack as follows:

Each new calling to the same function adds a new process in the stack.

Upon reaching the base case, the function finally has a reference point on which to perform the following operations. In the case of the example, it has calculated the power of ³⁴ reaching up to ³⁰, which was defined as exactly 1. Then, it frees memory for the case that is higher on the stack and continues executing the missing subroutines, until it reaches the beginning and returns us the final answer:

After having reached the base case, the function returns a value, in this case 1, then continues with the next case, to which it multiplies the returned value by x, which gives as value 3 in this case. It returns the new value and the memory of this subroutine is freed. The returned value is multiplied by 3 in the next process, returning 9 and freeing the memory allocated to the process. This will keep repeating until we reach the main case, returning 81 and freeing the last remaining subroutine from the stack.