Recursion
Computer languages allow a function or a module to call itself, this technique is known as recursion. It can go infinite like a loop, therefore to stop it from going on infinitely there are two properties that a recursive function has:
- It must have at least one base criteria.
- The recursive calls must have a progressive approach, so that every time a call is made, it is closer to the base criteria.
Implementation of recursion
Recursion can be implemented by means of stacks. A function calls another function, and transfer the execution to the second function. This transfer process may also include the exchange of data.
An activation record or stack frame is made for the first function or the caller to hold the values it was working with, as it needs to suspend its execution temporarily.
Analysis of recursion
Recursion makes a program more readable and is more efficient than iteration.
Time complexity
In recursion, it needs to figure out the number of times a recursive call is made. Assuming a call made to a function is O(1), then the number of times a recursive call is made, makes the recursive function O(n).
Speed complexity
In recursion, the system needs to store an activation record each time a recursive call is made. Therefore, the space complexity of a recursive function may go higher than that of a function with iteration.
Reference