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

1 public final class PrintInt
2 {
3 private static final String DIGIT_TABLE = "0123456789abcdef";
4 private static final int MAX_BASE = DIGIT_TABLE.length( );
5
6 // Print n in any base, recursively
7 // Precondition: n >= 0, 2 <= base <= MAX_BASE
8 private static void printIntRec( long n, int base )
9 {
10 if( n >= base )
11 printIntRec( n / base, base );
12 System.out.print( DIGIT_TABLE.charAt( (int) ( n % base ) ) );
13 }
14
15 // Driver routine
16 public static void printInt( long n, int base )
17 {
18 if( base <= 1 || base > MAX_BASE )
19 System.err.println( "Cannot print in base " + base );
20 else
21 {
22 if( n < 0 )
23 {
24 n = -n;
25 System.out.print( "-" );
26 }
27 printIntRec( n, base );
28 }
29 }
30 }

figure 7.4
A robust number-
printing program

7.3.2 why it works

In Theorem 7.3 we show, somewhat rigorously, that the printDecimal algo-
rithm works. Our goal is to verify that the algorithm is correct, so the proof is
based on the assumption that we have made no syntax errors.

The proof of Theorem 7.3 illustrates an important principle. When
designing a recursive algorithm, we can always assume that the recursive calls
work (if they progress toward the base case) because, when a proof is per-
formed, this assumption is used as the inductive hypothesis.
At first glance such an assumption seems strange. However, recall that
we always assume that method calls work, and thus the assumption that the
recursive call works is really no different. Like any method, a recursive rou-
tine needs to combine solutions from calls to other methods to obtain a solu-
tion. However, other methods may include easier instances of the original
method.

Recursive algo-
rithms can be
proven correct with
mathematical
induction.