Go Deeper!

In this article, the beauty and power of recursion will be exposed and explained. The idea is to explain this concept, the characteristics of any recursion function, and with an example analyze what is happening in each level of the stack.

Recursion functions are the ones that in a point of their body, they call themselves. All recursion function have two cases. One is the Base Case and the other is the Recursive Case. The Recursive Case is where the function calls itself and then returns. The Base Case is where the function returns without calling itself, as its name indicates, it is the Base of the end of the recursion, this is what allows this type of functions to not run for ever, because the have reached the Base Case.

So to recall, there is a recursive function, by a series of conditional statements the can fall into the Recursive Case or the Base Case. The key for them to work if for each recursive call, it has to advance one step closer to the Base Case. This is very important because even though if it has a Base Case, but the recursive Case does not advance towards it, it will run for ever.

To make things clearer, an analogy with dreams can be made. The first time the function is called, is like the real world, and every time the recursion (meaning, the same function is called within the function) is like entering a dream. When another recursion is called, then it is a dream within a dream, but in everydream, there is something different, something has changed slightly that is one step closer to a limit. This can keep going until a limit is reached, the final dream has been reached (in technical terms, the Base Case). Once this happens, it starts a process of "waking up", every level of deeper dreams, start to wake up in that same reversed order.

This order is like a stack, in the order the stacks are stacked, they are reversly de stacked.

This are te basic concepts of Recursion. A function that calls itself, where there is a Recursive Case, where in each call, there is something in the parameters that make it one step closer to the Base Case, which is the final case where there is no more recursion, and a return is made. Once this return is made, a destacked or "waking up" starts to occur until the getting back to the first original function.

This an alternative for using loop iterations. Sometimes it is preferred because once it is mastered, it's code is elegant and simple.

There are other aspects to take into account because this can be treacky at first. Getting mentally lost and actually don't know what it will do at a certain level can be frustrating.

So to clear this up, this drawing can help. All the code written in a Recursive Function that is done before reaching the call of the recursive case, will be done in straight forward order. So for example printing each character of a string until reaching the end. If the print of each character is done before the recursive call, then it will print it in order. Now, to print a string backwards, then it must first reach the end of the string, meaning reachin the base case. Once it is reached, it returns, and starts "waking up", that means that when it goes back to the previous stack, it can still run code, in this case, the print statement will go after the recursive call so this line of code will be read only when the base case is reached and returned. This makes it possible to do things in reverse order. If printing the character is called after the recursive call, then it will print the string backwards.

This concept is very important. In more complex functions, it helps to have clear what it will do in straight forward order, and in backwards order.

Another very important thing is to remember that the Base Case must be reachable. As mentioned this is done by at least two aspects. The first is to actually have a Base Case and that the Recursive Case parameters advances towards the base case. But normally the base case and recursive case are mutually exclusive, so this means that a conditional statement must be made in order to enter to either case. So this means checking for either the Base Case or Recursive case with an if statement. Knowing this also allows to clarify that other line codes cand be made only when the recursive case is identified or only when the Base Case is identified.

Knowing and making a whiteboard of what wants to be done in straightforward order, in reverse order, only when in recursion case or only when base case is reached is very important to master Recursive Functions.

Now a real and powerful recursive function will be analyzed and parsed into this same aspects. Then a numeric example will be introduced and analyzed in slow-motion to look what happens in every stack level.

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 is the function to analyze, a power recursion.

float _pow_recursion(float x, float y)
{
    /* Base Case */
    if (y == 0)
        return (1);

    /* Recursive case #1 */
    if (y < 0)
        return (_pow_recursion(x, y + 1) / x);

   /* Recursive case #2 */ 
   return (_pow_recursion(x, y - 1) * x);
}        

Introduction to a mathematical power function:

Starting by the math, it is important to understand that a power is a base number "x" that will be multiplied by itself "y" times. So when we have 6 to the power of 3 it will look like this: 6 * 6 * 6

Now, something interesting happens when the the exponent (in this case the "y") is negative. Mathemathically is the same as dividing:

x ^ (-y) = 1 / (x ^ y)

With a numeric example expanding it it will be: 6 ^ (-3)

6 ^ (-3) = 1 / (6 ^ 3) = 1 / (6 * 6 * 6) = 1 / 6 / 6 / 6

The last one to any one that does not know the mathematical order, will be confused but the operations are done from left to right, meaning it divides 1 by 6 three consecutive times.

The last thing to detail is that it is a mathematical property that any number to the exponent of 0 is equal to 1

x ^ 0 = 1

Explaining Recursion:

The Base Case:

When analyzing a power function, it is a known mathematical property of x ^ y is translated as the base case, since this mathematical truth let us know the base where the exponent is true no matter the base of the exponent.

Recursive Cases:

Now to solve the different cases that one may have for a power where y might be positive or negative, two recursive cases must be made.

Recursive Case #1: where "y" is negative:

As detailed earlier, a negative y implies a division of 1 by an "x" number "y" times.

This is translated to the recursive case where we will dived the return of the recursive function, where it will inevitably will lead to the base case where 1 is returned. So one can assure that after the return of the base case, 1 will be the numerator, and it will be divided by x. Now every time it goes back from the deepest stack, or "waking up" it will divide that result again by x. So as detailed earlier, to be clear lets parse a little the function to see it clearer:

float _pow_recursion(float x, float y)
{
    /* Base Case */   Done stright foward order
    if (y == 0)
        return (1);

    /* Recursive case #1 */
    if (y < 0)
        return_value = _pow_recursion(x, y + 1)
        temp_result = return_value / x     This is done in backwards order             
                                           after reaching base case
        return (temp_result)

   /* Recursive case #2 */ 
   return (_pow_recursion(x, y - 1) * x);
}        

Now it is visible that the divisions

Becase as we will see, if y is negative or positive in the recursive case, it will always advance towards making y 0.