When to use recursion
There have been two main criticisms of recursion:
It takes longer to execute than an iterative version
It is hard to understand
In the early days of software development, the technique was even barred in some organizations.
While a recursive version may take longer, for many problems this efficiency issue is not a significant concern given the improved processing speed on modern machines. Recursive efficiency issues lie with its typical implementation using a program stack. It is the pushing and popping of the activation record during method invocation that is expensive. This concept was detailed in Understanding the program stack.
Not all problems are suited for recursive solutions. Recursion should be used when:
The problem lends itself to a recursive solution
The number of recursive calls are not excessive
Maintainability is important
Some problems are naturally solved by recursion. Most tree problems are of this nature. For some problems, an iterative solution is not always...
