How recursion works & .... other stuff !

Recursion. The word alone brings back some painful and confused memory to every CS dev. You didn’t do much recursion the last 2 trimesters of glorious copy past from Stack Overflow. Where to begin?

You begin to search the deep Internet, and you stumble upon this article. Welcome, dear reader!, today we're going to unravel the recursion net.

What's recursion?

In fact is a process in wich a function calls itself directly or indirectly.

(On right side we have our recursion function (box) , and the other side in fact whats happening)

Recursive functions use something called “the call stack.” When a program calls a function, that function goes on top of the call stack. This similar to a stack of books. You add things one at a time. Then, when you are ready to take something off, you always take off the top item.

Before to jump , to stack , we need to know which steps leads us there:

Recursive Case

The concept of the recursive case is crucial towards developing useful recursive functions. A function that calls itself with the same parameters will just lead to an infinite state of sameness as we saw in the previous example. A key component of useful recursive functions is that the function call itself with different parameters — the recursive case.

Base Case

The last component of a useful recursive function is the?base case. The base case is a condition which a function can return the result without another call to itself. It is the condition at which the recursive calls will terminate, and yield a function that will not produce endless output.

Call Stack

However, with more complex recursive functions, behaviors that can’t be easily interpreted from reviewing the source code alone emerges. Note the following example of a recursive C function which returns the power of two integers passed in as parameters:

#include <stdio.h>

int _pow_recursion(float x, float y)
{
        if (y < 0)
        {
                return (-1);
        }
        if (y == 0)
        {
                return (1);
        }
        return (_pow_recursion(x, y - 1) * x);
}
int main(void)
{
        int result;
        result = _pow_recursion(2, 2);
        printf("result is: %d\n", result);
        return (0);
}        

The output will be the result of 2 raised to the power of 2:

result is: 4        

Notice there is both a base case to terminate the function calls, and a functional recursive case, which decreases the exponent value each time the function is called. See the commented function below:

int _pow_recursion(float x, float y)
{
/*Checks for negative exponents, this function returns -1 */
        if (y < 0)
        {
                return (-1);
        }
/*Base case, when the exponent reaches 0, return*/
        if (y == 0)
        {
                return (1);
        }
/*Recursive case, call the function again, decreasing the exponent*/
        return (_pow_recursion(x, y - 1) * x);
}        

However, to follow the execution of this program, one has to understand the flow of the?call stack. The call stack is mysterious because it operates behind the scenes, handling functions without explicit instructions from the user. A stack is a type of data structure where values can only be added or removed from the “top” of the stack. A call stack is a stack of?frame objects, which is the information from a single function call. Each time a function is called, a new frame object is placed onto the top of the call stack.

New frame objects are created each time a call to a function is made, and it is not until a base case is reached, and the function returns, that frame object is removed from the top of the stack. With each frame object removal, the data cascades down, until the initial function call can be resolved. The following diagram is a visual representation of what happens in the stack with the function?_pow_recursion()?called to return 2 to the power of 2:

(A diagram of a recursive function that returns the power of two positive integers).

One last thing that should be mentioned now that the concept of the stack is introduced, is that each time a frame object is added to the stack, more memory is used. In the case of our recursive functions without base cases, it actually doesn’t produce infinite output as it would with with infinite iterative loops. Since stack memory is used with each function call, and the functions call without end, the result is a?stack overflow, a terminal error during execution.

A general flow of the execution of recursive functions can be stated as:

Initialize the function with data. > Check to see whether the current value(s) being processed match the base case. If so, process and return the value. > Redefine the answer in terms of a smaller or simpler sub-problems > Run the algorithm on the sub-problem. > Combine the results in the formulation of the answer. > Return the results.

Concluding

Even with all the concepts grasped, like any aspect of programming, to effectively use recursion, it takes practice to master. Hope that this article , could be helpfull to you.

See ya!