Recursion vs. Iteration

Recursion is an alternative form of looping (iterations). It is essentially repetition without a loop. 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.

Recursion Advantages

Any problem that can be solved recursively can be solved non-recursively with iterations. Recursion has some 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 for an inherently recursive problem a clear, simple solution that would otherwise be difficult to obtain. Examples are the directory-size problem, the Towers of Hanoi problem, and the fractal problem, which are rather difficult to solve without using recursion.

When to use Recursion and when Iteration?

The decision whether to use recursion or iteration should be based on the nature and your understanding of the problem you are trying to solve. The rule of thumb is to use whichever approach 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.

Reference(s): Introduction to JAVA by Y. Daniel Liang

No comments:

Post a Comment