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

Factorial.java The routine shown in Figure 7.10, for computing
factorials.
BinarySearchRecursive.java
Virtually the same as BinarySearch.java (in Chap-
ter 6), but with the binarySearch shown in
Figure 7.11.

Ruler.java The routine shown in Figure 7.13, ready to run. It

contains code that forces the drawing to be slow.

FractalStar.java The routine given in Figure 7.15, ready to run. It

contains code that allows the drawing to be slow.

Numerical.java The math routines presented in Section 7.4, the pri-

mality testing routine, and a main in RSA.java that
illustrates the RSA computations.

MaxSumTest.java The four maximum contiguous subsequence sum

routines.

MakeChange.java The routine shown in Figure 7.25, with a simple main .

TicTacSlow.java The Tic-Tac-Toe algorithm, with a primitive main .

See also Best.java .

exercises

IN SHORT
7. 1

What are the four fundamental rules of recursion?

7. 2

Modify the program given in Figure 7.1 so that zero is returned for
negative n . Make the minimum number of changes.

7. 3

Following are four alternatives for line 11 of the routine power (in
Figure 7.16). Why is each alternative wrong?

long tmp = power( x * x, n/2, p );
long tmp = power( power( x, 2, p ), n/2, p );
long tmp = power( power( x, n/2, p ), 2, p );
long tmp = power( x, n/2, p ) * power( x, n/2, p ) % p;

Show how the recursive calls are processed in the calculation 2 63 mod 37.

7. 4

Compute gcd(1995, 1492).

7. 5

Bob chooses p and q equal to 37 and 41, respectively. Determine accept-
able values for the remaining parameters in the RSA algorithm.

7. 6

Show that the greedy change-making algorithm fails if 5-cent pieces
are not part of United States currency.

7. 7