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

Recursion has many uses, some of which we discussed in this chapter. Three
important algorithm design techniques that are based on recursion are divide-
and-conquer, dynamic programming, and backtracking.
In Chapter 8 we examine sorting. The fastest known sorting algorithm is
recursive.

key concepts

activation record The method by which the bookkeeping in a procedural lan-
guage is done. A stack of activation records is used. (303)
alpha-beta pruning An improvement to the minimax algorithm. (336)
backtracking An algorithm that uses recursion to try all possibilities. (333)
base case An instance that can be solved without recursion. Any recursive call
must progress toward a base case. (298)
basis In a proof by induction, the easy case that can be shown by hand. (296)
divide-and-conquer algorithm A type of recursive algorithm that is generally
very efficient. The recursion is the divide part, and the combining of
recursive solutions is the conquer part. (319)
driver routine A routine that tests the validity of the first case and then calls the
recursive routine. (300)
dynamic programming A technique that avoids the recursive explosion by
recording answers in a table. (329)
encryption An encoding scheme used in the transmitting of messages that can-
not be read by other parties. (317)
Fibonacci numbers A sequence of numbers in which the i th number is the sum
of the two previous numbers. (304)
greatest common divisor (gcd) The greatest common divisor of two integers is
the largest integer that divides both of them. (314)
greedy algorithm An algorithm that makes locally optimal decisions at each
step—a simple but not always correct thing to do. (329)
induction A proof technique used to establish theorems that hold for positive
integers. (295)
inductive hypothesis The hypothesis that a theorem is true for some arbitrary
case and that, under this assumption, it is true for the next case. (296)
leaf In a tree, a node with no children. (306)
minimax strategy A strategy used for Tic-Tac-Toe and other strategic games,
which is based on the assumption of optimal play by both players. (334)
multiplicative inverse The solution

1 XN ≤ < to the equation AX ≡ 1(mod N ).

(315)