Learn Recursion

DEFINITION :

Recursion is a process that refers to the very object of the process at a point in the process. In other words, it is an approach whose description leads to the repetition of the same rule.

EXAMPLE:

Take a look at the following algorithm that calculates a number x taken to the power of 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);
}

The base case in this function is when y equals 0. The other if statement “if y < 0” is there as a safeguard against the user trying to raise a number to the negative power and can be ignored in this recursion discussion.

Let’s step through a simple example and see what happens in the stack at each recursive step.

Say we want to perform the calculation ³⁴. Using the function above, the first time the function gets called, x will be 3 and y will be 4. On the call stack, it can be pictured as follows(bottom to top, remember Last In, First Out):

let’s execute it manauly with x = 3 et y = 4 :

In the diagram above, the main function is represented as the bottom most block (0) and the next block up (1) is the first call to _pow_recursion. Execution of the code goes from block 0 to block 5, each block is paused after a new block is added above and waits. Then, once the base condition is met and the top most block completes execution, the process reverses and each function runs to completion from top to bottom and returns the result until we finally get back to main (0) and arrive at the final result. Visually, one can follow the arrows in the diagram above starting from the bottom left (0) up to the top (5), then going to the right and following the arrows down until arriving back at main (0).

Walking through the code, the main function is the entry point into the program, inside main, the recursive function _pow_recursion is called with x = 3 and y = 4. The actual function call will look like the following:

result = _pow_recursion(3,4);

Within the _pow_recursion function, the first few lines of code are a couple of if statements. As discussed earlier, the first if statement “if y < 0” is a safeguard against an infinite loop condition if negative y value is used.

The next if statement “if y == 0” is the base case or stop condition. This statement will stop the recursion and just return the value 1 to the calling function.