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...