Recursion
Recursion can be a complex topic to understand, even for the most experienced programmer. In this little blog, we will try to explain recursion simply so that the basic concepts behind recursion are as clear as possible.
What is recursion?
When we write a program to perform a specific task we can use that function by calling it. A typical example of a recursive function is finding the factorial number:
4! = 4 * 3 * 2 * 1 = 24
To find the factorial of 4, it is necessary to multiply the numbers from 4 to 1. We can see that each multiplication is the previous number -1. This can be summarized as follows:
n! = n * (n — 1) * (n — 2) * (n — 3)
And we could summarize it even more as:
n! = n * (n — 1)!
As we can see in the previous image, the second part of the equation is the same variable n! applied to a different number (n -1). And this is repeated until the number n is equal to 1.
In this way, we can continue repeating that same operation with each (n -1) … a repetitive operation. In this case, it is possible to call the same function to execute the same operation on the same number -1 … and so on.
Now let’s talk about stacks…
Stacks are data structures in which the first element to enter is the last to leave. An example from everyday life is a stack of dishes. When we have the dishes in the dishwasher and we wash them we are stacking one on top of the other, but when we are going to use a plate again we take the one that is at the top, which was the last one we put in the sink when washing it.
The concept of stacks is important in recursion. When writing a recursion program, each time the function is called a new copy of the method is created in a part of memory known as the stack. All the variables and other elements that we have declared within our function will be temporarily stored in the memory stack. Once the end of the calls is reached and the value of each call is returned, that part of the stack is eliminated.
This information, like the stack of dishes, is stored one on top of the other. Once the calls to the function are finished, the return of the values and the destruction is done.
Memory and resource management:
As you might have guessed, recursion can be a huge drain on both computational and memory resources. Although recursive code is more compact, often easy to write and understand … the truth is that recursion is not faster. And there are few occasions in which its use is recommended over the iterative solution.
In the following table we can observe a few differences between iteration and recursion:
But then why choose recursion?
There are complex problems that are recursive in nature and, are easier to implement with algorithms of this type. Sometimes the recursive solution offers a solution that is easier to understand and debug. It is useful for tasks that can be defined in similar subtasks as sorting, searching, and traversal problems. Some solutions that are better in recursion: Tower of Hanoi, Fibonacci series, factorial finding…
However, the solution must be iterative under unfavorable time and memory conditions since the recursion uses additional time and memory.
Remember: any problem that can be solved recursively can also be solved iteratively. When no substantial improvement is seen using recursion, an iterative solution should be preferred.
Some things to keep in mind when doing recursive functions:
- A recursive function must have a termination condition otherwise, it can continue indefinitely. This is known as an exit condition or base component. The base component is a condition in which the function is defined directly (not recursively) and that is solved with a simple statement. This allows the program to stop the recursive call. In the factorial example, the base case would be when n equals 1 because at that moment we would calculate the factorial of 0 and it goes there because in negative numbers there is no definition of factorial.
- In each recursive call, it must be ensured that the function approaches a response or output. In the case of the factorial, it would be n — 1, which decreases the value of n until it reaches 1. n! = n * (n — 1)!
Now, the __pow_recursion!
Now we are going to see it with a specific case. In this case, we have a function that will return the power of a number y.
And now let’s see what happens in the memory stack with each step:
Just like a stack, the memory stack works the same way. The first element to come in is the last to come out, storing function calls and required variables.
In conclusion:
A recursive function carries out tasks by dividing them into smaller tasks. There is a termination condition, defined in the function, that is satisfied by some specific subtask. After this, the recursion stops, and the final result is returned from the function.
To remember: three conditions are necessary for the construction of a recursive function:
1 A base case, up to which recursion occurs.
2 A recursive call that allows the recursion to continue
3 A final case that allows ending the recursion
References:
- Luis Joyanes Aguilar. Programacion en C. Metodología, algoritmos y estructura de datos
- Luis Joyanes Aguilar, Ignacio Zahonero Martinez. Programacion en C, C++, Java y UML. Mc Graw Hill.
