Hello to myself

What is recursion?

According to wikipedia and geeksforgeeks recursion is when something is define in terms of itself or of it’s type.

In this case for programming we can say that recursion is a function that calls itself.

In order to make a recursive function first we need to know that it’s necessary to determine a base condition, usually associated with a problem that is no possible to divide or unglobe.

For example, whenever we call a function in C, the local variables and function parameters are stored in stack memory, the data are stored and removed in a LIFO (last in, first out) pattern.

This is how it works. When a function requests space for local variables, the allocated space is added to the top of the stack. When the end of the function is reached, the space allocated for local variables appears at the top of the stack.

Variables are stored in stack-based memory that can’t be dynamically allocated during program execution. However this type of memory allocation performs heap-based storage.

Stack overflow can happen due to the limited space available for stack-based memory, but it is just as necessary to define the base condition. One of the most common causes of stack overflow is infinite recursion, a behavior we must be aware of when programming recursive functions.

Let’s take a look at this example of an 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);
}

Here we can see a code in a recursive form but… how recursion works?

How recursion works?

1. Stacking

The function calls itself, and if the base condition is not met, it calls itself again meanwhile a stack of new local variables and parameters is added to the exsiting memory stack

As we can see when the base case is reached the magic happens, and this base case is used to answer the previous calls.

And finally, the last stack is removed and the final response is obtained.