Recursion…

Recursion, in programming world, is a topic that many do not like and avoid talking about it. It is tedious to try to figure out what a piece of code does when it is called recursively. But the moment comes when recursion is the only way we have left to solve a problem and we cannot escape from it. Well, I think I speak for myself, actually I don’t know how many other programmers feel the same way.

Recursion, in computer science, is a method of solving a problem where the solution depends on solutions of smaller instances of the same problem. Recursion solves problems by using function that call themselves from within own code

I will try to explain it with the following piece of code written in 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);
}

The parts of the function

Test cases

For test cases I will choose:

1. Two numbers, x equals to 2 and y equals to 3
2. Two numbers, x equals to 2 and y equals to -3

First test case

Each time that the function is called, all the information is stored in the stack

Now the stack is freed (information stored in it)following the LIFO method

Now we know that this piece of code computes x to the power of y recursively.

Second test case

In this order, 2 to the power of -3 will return 0.125, but in this case the function is calling itself in line 6

When using recursion or iteration sometimes it becomes a matter of taste, but without a doubt there are operations that are made much easier to perform through recursion and more if it is about operations on complex data structures such as binary trees. But, considering the code example above, memory consumption is the Achilles’ heel of recursion

Recommended

Recursive programming

Recursion and Memory Visualization