Recursion…

Russian dolls example

Recursion is the process in which a function calls itself. It is a method used by programmers where the solution depends on solutions to smaller instances of the same problem.

Terms to know before example:

• Base case: Also called as the exit condition since it represents the condition at which the recursive function will stop calling itself, preventing by that an infinite loop.

*If the base case is not reached or not defined, then the stack overflow problem may arise

• Stack: Is an abstract data type used to collect elements. Have two main operations:

1. Push, which adds an element to the collection.
2. Pop, which removes the most recently added element that was not yet removed.

• Heap: The entire block of memory accessible and available. Only restriction is the capacity of your computer.

Example:

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

First of all we clarify the base case or exit condition, which is:

if (y == 0)
    return (1)

We’re going to calculate 2 taken to the power of 6: _pow_recursion(2, 6)

As you can see the variable y = 6 does not meet the base case y == 0 at first, so it takes the elevator to go to the next floor until it meets the base case at the 7th stack.

! Keep in mind: A Stack is an organize pile with LIFO order

Meaning that the Last In is the First Out. This means that the first item to be stacked, is the last one to be removed. Meaning that the last one to be added will be the first one to be removed.

Going back to the building example:

Now that we reached the exit condition, “y” will go back in the elevator up to the penthouse which is the 1st stack, representing the return value of 1.

return (_pow_recursion(x, y - 1) * x);

Upon receiving 1 from the previous floor, next floor will multiply the received value by its known “x” (accessible from stack), then it will go up each floor doubling its value since its multiplying by “x” which is equal to two.