Java Reference
In-Depth Information
step. Similarly, the recursive solution calls itself between n/2 and n times, because
one or two characters are removed in each step.
Occasionally, a recursive solution runs much slower than its iterative counterpart.
However, in most cases, the recursive solution is only slightly slower.
In such a situation, the iterative solution tends to be a bit faster, because each
recursive method call takes a certain amount of processor time. In principle, it is
possible for a smart compiler to avoid recursive method calls if they follow simple
patterns, but most compilers don't do that. From that point of view, an iterative
solution is preferable.
607
608
There are quite a few problems that are dramatically easier to solve recursively than
iteratively. For example, it is not at all obvious how you can come up with a
nonrecursive solution for the permutation generator. As Exercise P13.11 shows, it is
possible to avoid the recursion, but the resulting solution is quite complex (and no
faster).
In many cases, a recursive solution is easier to understand and implement correctly
than an iterative solution.
Often, recursive solutions are easier to understand and implement correctly than their
iterative counterparts. There is a certain elegance and economy of thought to
recursive solutions that makes them more appealing. As the computer scientist (and
creator of the Ghost-Script interpreter for the PostScript graphics description
language) L. Peter Deutsch put it: ȒTo iterate is human, to recurse divineȓ.
S
ELF
C
HECK
7.
You can compute the factorial function either with a loop, using the
definition that n! = 1 ¶ 2 ¶ ș ¶ n, or recursively, using the definition
that 0! = 1 and n! = (n ɨ 1)! ¶ n. Is the recursive approach inefficient in
this case?
8.
Why isn't it easy to develop an iterative solution for the permutation
generator?
