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

public key cryptography A type of cryptography in which each participant pub-
lishes the code others can use to send the participant encrypted messages
but keeps the decrypting code secret. (318)
recursive method A method that directly or indirectly makes a call to itself.
(297)
RSA cryptosystem A popular encryption method. (317)
rules of recursion 1. Base case: Always have at least one case that can be
solved without using recursion (298); 2. Make progress: Any recursive
call must progress toward a base case (298); 3. “You gotta believe”:
Always assume that the recursive call works (302); 4. Compound interest
rule: Never duplicate work by solving the same instance of a problem in
separate recursive calls. (305)
telescoping sum A procedure that generates large numbers of canceling terms.
(326)
tree A widely used data structure that consists of a set of nodes and a set of
edges that connect pairs of nodes. Throughout the text, we assume the
tree is rooted. (306)

common errors

1.

The most common error in the use of recursion is forgetting a base case.

2.

Be sure that each recursive call progresses toward a base case. Otherwise,
the recursion is incorrect.

3.

Overlapping recursive calls must be avoided because they tend to yield
exponential algorithms.

4.

Using recursion in place of a simple loop is bad style.

5.

Recursive algorithms are analyzed by using a recursive formula. Do not
assume that a recursive call takes linear time.

on the internet

Most of the chapter's code is provided, including a Tic-Tac-Toe program. An
improved version of the Tic-Tac-Toe algorithm that uses fancier data struc-
tures is discussed in Chapter 10. The following are the filenames.

RecSum.java The routine shown in Figure 7.1 with a simple main .

PrintInt.java The routine given in Figure 7.4 for printing a num-

ber in any base, plus a main .