What is Recursion? Computer science

Every day of our lives we usually find notions to interpret the reality from where we are living, and how we perceived also defines many concepts in computer sciences, one of them is recursion. The hard meaning of that is the way to specify a process based on its own meaning. But this idea seems too ethereal and we need way more to fully understand it and even more how to apply it.

One interesting example that will help us to understand is in our own biology, as every living being on the planet our goal as a species is getting food, reproduce and survive, and this is a process those have been doing generation after generation. And These kinds of goals and challenges are similar to unicellular beings, those from what we are made of. So, in a specific moment at the evolution race it result, the best way to solve a common problem was to work together in a common solution. We can scale this idea into society like ants colonies and even more like ecosystems.

And how can we apply this concept to solve complex mathematical problems? Well sometimes we can reduce the size of a big problem into many smaller pieces of itself, we may be able to create a solution for one of these smaller versions and then be able to find for the whole task. This is the idea behind the concept of Recursion. It is a solving computer technique that involves the uses of procedures, functions, algorithm, or subroutines whose objective is to call itself until finding a termination condition, so successive repetitions are processed up to the critical step where the condition is met at which time the rest of each repetition is processed from the last one until the first call.

Example

To put the ideas into practice we will solve a simple exercise where we are creating a function to replicate the operation exponentiation using recursion in C language and analyze how the information is stored in the memory stack following the next code.

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

int main (void)
{
    x = 4;
    y = 3;

    result = _pow_recursion(x, y)

    return (result);
} 

In this case, our function receives two parameters, x will represent the base and y the power. As you may know, the first condition of our program is defined by the exponentiation's property of any number at 0 power will be equal to 1, it will also work as our termination condition. The second and third parameter of the equation will call itself I using the recursion concept we just previously mentioned, they will operate differently depending on if we introduce a positive or negative power, if y is positive it will call it self multiplying the x but reducing the power by 1, and repeat this process until reach the condition y = 0, a mathematically way to look it will be like this.

Using the example showing before is an easy way to understand recursion, but we want a closer approach to how actually the machine will interact with its data, and we will do so using the stack memory diagram.

The previous diagram shows how the function (_pow_recursion) stacks together in the memory execution. First, we will declare our variables in the main as we see it will be exported to the function without any modification, now when we enter to the function is where the magic happens, it will continually create new functions in the stack until the condition of y = 0 become truth and then they will be executed in descending order, and the result would be similar to the one we show in the mathematical diagram. Now we understand the concept and how to apply it there are some considerations when you are using recursion, those presented are probably the most relevant of all.

Escalation

Be sure during the approach of the problem go from a small size into a bigger one, and every step of the solution works as an interative interpretation of itself, there could be some differences but you must be prepared, taken into account and doing the appropriate correction to your cod for correct function.

Avoid endless loops

Another problem to avoid when writing recursive functions is circularity. Circularity occurs when you reach a point in your recursion where the arguments to the function are the same as with a previous function call in the stack. If this happens you will never reach your base case, and the recursion will continue forever, or until your computer crashes, whichever comes first.