Recursion
The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function. Using a recursive algorithm, certain problems can be solved quite easily. A recursive function solves a problem by calling a copy of itself and solving smaller subproblems of the original problems.It is essential to know that we should provide a certain case in order to terminate this recursion process.
When we call a function (or method) the process is as follows
- Space is reserved on the stack for function parameters and their local variables.
- The address of the code line from which the method was called is saved on the stack.
- Function parameters and their values are stored on the stack
- Finally, the allocated memory is released on the stack when the function ends and it returns to the original code call.
Instead, when the function is recursive. Each call generates a new function call with corresponding local objects. Re-executing completely, until the call itself. Where it recreates on the stack the new parameters and local variables. As many as recursive calls we generate. When finished, the memory is freed on the stack, starting from the last function created to the first, which will be the last to be freed.
One important thing to note is that every time a function is called from another function (even to itself), a new entry is created in the interpreter's call stack. This has a limited space so there may come a point where if you do too many it becomes saturated and an error occurs. This error is called "Stack Overflow".
Recursion example
An example that is easy to see and often used is the calculation of the factorial of an integer. The factorial of a number is defined as that number multiplied by the previous one, this number multiplied by the previous one, and so on until reaching 1. Thus, for example, the factorial of the number 5 would be: 5x4x3x2x1 = 120.
An example of this procedure in c would be this:
The same but with recursion and without using any loop could be done this way
Here I attach the link of a video where it is explained what happens behind this function:
An example with the factorial of 4:
Advantages and disadvantages of the recursion:
Advantages:
- Solutions to complex problems in an easier, simpler, clearer and more elegant way.
- It is not necessary to define the exact sequence of steps to solve the problem.
- We can consider that "we have solved the problem" (smaller).
- The efficiency of recursion lies in the fact that it can be used to solve problems that are difficult to solve iteratively.
- Some problems are easier to implement using recursion.
- It presents a facility to check and verify that the solution is correct.
Disadvantages:
- inefficiency
- Overhead associated with calls to subalgorithms.
- A single call can generate a large number of recursive calls. (Fact(n) generates n recursive calls.)
- Algorithm clarity may not compensate for algorithm overhead
- Inefficient recursive algorithms.
- It is necessary to create many variables which can cause problems in memory.
- In general, a recursive function takes longer to generate than an iterative one.
- Due to constant method calls, creation of dynamic variables on the stack, and duplication of variables.