RECURSION

In the programming languages, there’s a method to solve problems called Recursion, and it consists on a Function that calls itself to turn the problem into small parts until it finds the solution.

Even though it’s not a commonly used method because of its great memory consumption and its syntax isn’t easy to read, it’s still an important tool and we need to learn how it works.

When talking about writing recursive functions, most people focus on the fact that any recursive function needs to have two parts:

1. A base case, in which the function can return the result immediately.
2. A recursive case, in which the function must call itself to break the current problem down to a simpler level.

This pattern can be seen very clearly in the next function, shown here in C:

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)
{
        int result;        result = _pow_recursion(3, 3);
        printf("result is: %d\n", result);
        return (0);
}

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

result is: 27

To follow the execution of this program, one has to understand the flow of the call stack. 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. The following diagram is a visual representation of what happens in the stack.

That’s it, I hope this little post will help you understand this important topic of recursion in computer science.

Next you can find some references that can help more.

References:

• https://www.freecodecamp.org/news/recursion-demystified-99a2105cb871/
• https://en.wikipedia.org/wiki/Recursion_(computer_science)

est14.dart@gmail.com