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

Note how we have a base case ( n is a one-digit integer), and because the
recursive problem has one less digit, all recursive calls progress toward the
base case. Thus we have satisfied the first two fundamental rules of recursion.
To make our printing routine useful, we can extend it to print in any base
between 2 and 16. 2 This modification is shown in Figure 7.3.
We introduced a String to make the printing of a through f easier. Each digit
is now output by indexing to the DIGIT_TABLE string. The printInt routine is not
robust. If base is larger than 16, the index to DIGIT_TABLE could be out of bounds.
If base is 0, an arithmetic error results when division by 0 is attempted at line 8.

The most interesting error occurs when base is 1. Then the recursive call at
line 8 fails to make progress because the two parameters to the recursive call are
identical to the original call. Thus the system makes recursive calls until it even-
tually runs out of bookkeeping space (and exits less than gracefully).

Failure to progress
means that the pro-
gram does not work.

We can make the routine more robust by adding an explicit test for base .
The problem with this strategy is that the test would be executed during each
of the recursive calls to printInt , not just during the first call. Once base is
valid in the first call, to retest it is silly because it does not change in the
course of the recursion and thus must still be valid. One way to avoid this
inefficiency is to set up a driver routine. A driver routine tests the validity of
base and then calls the recursive routine, as shown in Figure 7.4. The use of
driver routines for recursive programs is a common technique.

A driver routine
tests the validity of
the first call and
then calls the
recursive routine.

1 // Print n in base 10, recursively.
2 // Precondition: n >= 0.
3 public static void printDecimal( long n )
4 {
5 if( n >= 10 )
6 printDecimal( n / 10 );
7 System.out.print( (char) ('0' + ( n % 10 ) ) );
8

figure 7.2
A recursive routine for
printing N in decimal
form

}

private static final String DIGIT_TABLE = "0123456789abcdef"; figure 7.3

A recursive routine for
printing N in any base

1

2
3 // Print n in any base, recursively.
4 // Precondition: n >= 0, base is valid.
5 public static void printInt( long n, int base )
6 {
7 if( n >= base )
8 printInt( n / base, base );
9 System.out.print( DIGIT_TABLE.charAt( (int) ( n % base ) ) );
10 }

2. Java's toString method can take any base, but many languages do not have this built-in
capability.