Recursion - Data Structures and Problem Solving Using Java - page 299

the recursive definition of S ( N ) does not allow for N < 1. We can fix this prob-
lem by extending the definition of S ( N ) to include N = 0. Because there are no
numbers to add in this case, a natural value for S (0) would be 0. This value
makes sense because the recursive definition can apply for S (1), as S (0) + 1 is 1.
To implement this change, we just replace 1 with 0 on lines 4 and 5. Negative
N also causes errors, but this problem can be fixed in a similar manner (and is
left for you to do as Exercise 7.2).
A second problem is that if the parameter n is large, but not so large
that the answer does not fit in an int , the program can crash or hang. Our
system, for instance, cannot handle N 8,882. The reason is that, as we

have shown, the implementation of recursion requires some bookkeeping
to keep track of the pending recursive calls, and for sufficiently long chains
of recursion, the computer simply runs out of memory. We explain this
condition in more detail later in the chapter. This routine also is somewhat
more time consuming than an equivalent loop because the bookkeeping
also uses some time.
Needless to say, this particular example does not demonstrate the best use
of recursion because the problem is so easy to solve without recursion. Most
of the good uses of recursion do not exhaust the computer's memory and are
only slightly more time consuming than nonrecursive implementations. How-
ever, recursion almost always leads to more compact code.

≥

7.3.1 printing numbers in any base

A good example of how recursion simplifies the coding of routines is num-
ber printing. Suppose that we want to print out a nonnegative number N in
decimal form but that we do not have a number output function available.
However, we can print out one digit at a time. Consider, for instance, how
we would print the number 1369 . First we would need to print 1 , then 3 , then 6 ,
and then 9 . The problem is that obtaining the first digit is a bit sloppy:
Given a number n , we need a loop to determine the first digit of n . In con-
trast is the last digit, which is immediately available as n%10 (which is n for
n less than 10).
Recursion provides a nifty solution. To print out 1369 , we print out 136 ,
followed by the last digit, 9 . As we have mentioned, printing out the last digit
using the % operator is easy. Printing out all but the number represented by
eliminating the last digit also is easy, because it is the same problem as print-
ing out n/10 . Thus, it can be done by a recursive call.
The code shown in Figure 7.2 implements this printing routine. If n is
smaller than 10, line 6 is not executed and only the one digit n%10 is printed;
otherwise, all but the last digit are printed recursively and then the last digit is
printed.