22. Java Collections Framework

[Page 649 ( continued )]

19.8. Recursion versus Iteration

Recursion is an alternative form of program control. It is essentially repetition without a loop control. When you use loops , you specify a loop body. The repetition of the loop body is controlled by the loop-control structure. In recursion, the method itself is called repeatedly. A selection statement must be used to control whether to call the method recursively or not.

Recursion bears substantial overhead. Each time the program calls a method, the system must assign space for all of the method's local variables and parameters. This can consume considerable memory and requires extra time to manage the additional space.

Any problem that can be solved recursively can be solved nonrecursively with iterations. Recursion has many negative aspects: it uses up too much time and too much memory. Why, then, should you use it? In some cases, using recursion enables you to specify a clear, simple solution that would otherwise be difficult to obtain.

The decision whether to use recursion or iteration should be based on the nature of the problem you are trying to solve and your understanding of the problem. The rule of thumb is to use whichever of the two approaches can best develop an intuitive solution that naturally mirrors the problem. If an iterative solution is obvious, use it. It will generally be more efficient than the recursive option.

Note

Your recursive program could run out of memory, causing a StackOverflowError .

Tip

If you are concerned about your program's performance, avoid using recursion, because it takes more time and consumes more memory than iteration.