Recursion and how it works on the stack

Blender Recursion GIF By Adampizurny — http://gph.is/2iOSPvH

What is recursion?

Recursion is defined as a function that calls itself.

It is a fundamental concept in mathematics and computing. It offers a different alternative of implementing repeating structures (loops), where modules are made recursive calls.
It is the systematization of the performance of the same process repeatedly, over and over again, until a result is obtained.

What is the object or what is it used for?

It can be used in any situation in which the solution can be expressed as a sequence of movements, steps or transformations governed by a set of unambiguous rules.

The object of a function calling itself is to solve a large problem by solving smaller instances of the same problem.

It is based on applying the same solution logic to a base problem, and to all decompositions or subdivisions of it. The objective is to work under the premise divide and conquer.
Dividing the problem in a systematic way is to decompose or express the same problem through the representation of instances of the problem from which they start. In this way, we reiterate the process and take each instance to an expression that is sufficiently reduced to facilitate or simplify obtaining the solution.

To establish recursive functions, it is required to establish a base case, that is, a simple solution for a particular case (there may be more than one base case).
We are faced with a recursive case, when the solution involves reusing the original function on a recurring basis, with parameters that get closer to the base case in each recurrence.

The steps followed by the recursive case are the following:

1. The procedure calls itself
2. The problem is solved by treating the same problem of smaller size
3. The way in which the size decreases ensures that the base case will eventually be reached

However, if a function keeps repeating this action, how can we prevent a function from going into an infinite loop? We solve this using a base condition, a condition that is commonly associated with a problem that can no longer be exploded.

Whenever a function is called in C, the local variables and parameters of the function are stored using a stack-based memory allocation. In this type of mapping, the data is stored and removed in a LIFO (last in, first out) pattern.

For this reason, we must consider that when a function requests space for local variables, the allocated space is added to the top of the stack. So when the end of the function is reached, the space allocated for local variables appears at the top of the stack.
Therefore, we must bear in mind that variables that are stored in stack-based memory cannot be dynamically allocated pieces of memory during program execution. Instead, memory of this type uses a heap-based storage allocation.
An example of this type of memory is the memory obtained using the malloc function in C.

It is important to note that stack overflow can occur due to limited space available for stack-based memory. One of the most common causes of stack overflow is infinite recursion, a behavior that we must consider when programming recursive functions.

To better understand recursion in action, let’s consider the following algorithm (written in the C programming language):

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

And let’s see it through a simple mathematical example to understand, considering 2³. Let’s analyze the algorithm when we call with these parameters:

int main (void)
{ 
        float x;
 
        x = _pow_recursion (2, 3); 
        return (EXIT_SUCCESS);
}

Let us remember that the way to find a solution to our problem, decompose the problem into parts, until we reach the base case, and compose all the parts to obtain the result.
With the values used, let’s see what happens with the execution of our program and how its work on the stack:

Every time the function is called and the base case is not reached, the function behaves recursively by calling itself again. A stack of new local variables and parameters are added to the existing memory stack with every function call.

When the base case is reached, a domino effect occurs as the response obtained from the base case is used to answer the previous function calls. As soon as a call to a function has been “answered”, the stack associated with the function can be dropped!

Finally, when we draw the last pile, we are left with our final answer.

Now, let’s look at another type of example, let’s consider the use of floating point or non-integer numbers.

In the example above, we looked at the behavior of the function when integers were used. However, what happens when we use numbers that will never get close to the base case (y == 0)?

To do this, we update the main function with the following values, x = 3.5 and y = 3.8:

int main (void)
{ 
        float x;
 
        x = _pow_recursion (3.5, 3.8); 
        return (EXIT_SUCCESS);
}

Will it ever get to 0?

Segmentation fault! Here, we see that we have encountered a stack overflow. What does this mean? As we mentioned earlier, stack overflow occurs when we use up all the available storage that has been allocated to the stack-based memory allocation.

Why did this happened?

Because our value y cannot reach the base case (y == 0), our recursive calls can never cease until the stack memory is exhausted.

To improve this function, further steps can be taken to ensure that a base case can be reached for all values of y.

I want this post to be of help to those who read it, carrying it out is part of my training at Holberton Montevideo.

It will be until next time, happy learning!