What are the advantages and disadvantages of recursion?
Any algorithm implemented using recursion can also be implemented using iteration.
Why not to use recursion
- It is usually slower due to the overhead of maintaining the stack.
- It usually uses more memory for the stack.
Why to use recursion
- Recursion adds clarity and (sometimes) reduces the time needed to write and debug code (but doesn't necessarily reduce space requirements or speed of execution).
- Reduces time complexity.
- Performs better in solving problems based on tree structures.
For example, the Tower of Hanoi problem is more easily solved using recursion as opposed to iteration.
All algorithms can be defined recursively. That makes it much, much easier to visualize and prove.
Some algorithms (e.g., the Ackermann Function) cannot (easily) be specified iteratively.
A recursive implementation will use more memory than a loop if tail call optimization can't be performed. While iteration may use less memory than a recursive function that can't be optimized, it has some limitations in its expressive power.
Recursion means a function calls repeatedly
It uses system stack to accomplish its task. As stack uses LIFO approach and when a function is called the controlled is moved to where function is defined which has it is stored in memory with some address, this address is stored in stack
Secondly, it reduces a time complexity of a program.
Though bit off-topic,a bit related. Must read. : Recursion vs Iteration
For the most part recursion is slower, and takes up more of the stack as well. The main advantage of recursion is that for problems like tree traversal it make the algorithm a little easier or more "elegant". Check out some of the comparisons:
link