(^652) | Recursion
looping structure such as a while,for, or do. In recursion, a process is made to repeat by hav-
ing a method call itself. A selection statement controls the repeated calls.
Which is better to use—recursion or iteration? This question has no simple answer. The
choice usually depends on two issues: efficiency and the nature of the problem at hand.
Historically, the quest for efficiency, in terms of both execution speed and memory us-
age, has favored iteration over recursion. Each time a recursive call is made, the system must
allocate stack space for all parameters and local variables. The overhead involved in any
method call is time-consuming. On early, slow computers with limited memory capacity, re-
cursive algorithms were visibly—sometimes painfully—slower than the iterative versions.
On modern, fast computers, however, the overhead associated with recursion is often so
small that the increase in computation time is almost unnoticeable to the user. Except in cases
where efficiency is absolutely critical, then, the choice between recursion and iteration more
often depends on the second issue—the nature of the problem at hand.
Consider the factorial and power algorithms discussed earlier in the chapter. In both cases,
iterative solutions were obvious and easy to devise. We imposed recursive solutions on these prob-
lems merely to demonstrate how recursion works. As a rule of thumb, if an iterative solution is
more obvious or easier to understand, use it; it is probably more efficient. For other problems,
the recursive solution is more obvious or easier to devise, such as the Towers of Hanoi problem.
(It turns out that the Towers of Hanoi problem is surprisingly difficult to solve using iteration.)
Computer science students should be aware of the power of recursion. If the definition of a
problem is inherently recursive, then a recursive solution should certainly be considered.
13.5 Testing and Debugging
Recursion is a powerful technique when used correctly. Improperly used, it can result in
errors that are difficult to diagnose. The best way to debug a recursive algorithm is to con-
struct it correctly in the first place. To be realistic, however, we give a few hints about
where to look if an error crops up.Testing and Debugging Hints1.Be sure a base case exists. If there is no base case, the algorithm will continue
to issue recursive calls until all memory has been used. Each time the method
is called, either recursively or nonrecursively, stack space is allocated for the
parameters and local variables. If no base case is available to end the
recursive calls, the run-time stack eventually overflows. An error message
such as “STACK OVERFLOW ERROR” indicates that the base case is missing.
2.Be sure you have not used a whilestructure. The basic structure in a recursive
algorithm is the ifstatement. At least two cases must be provided: the recur-
sive case and the base case. If the base case does nothing, the elseclause is
omitted. The selection structure, however, must be present. If a while