Recursion solves a problem by repeatedly reducing it to smaller, similar problems. Each recursive call moves toward a base case with an immediate solution; returned results then unwind to solve the original problem. section 15.1 section 15.11
Table 15.1 Comparing a for loop to recursion
|
|
Recursion |
|
| Initial condition |
|
The original problem |
| Repeated updating |
Set i to the next value in the range. |
Reduce the problem into a smaller but similar problem. |
| Terminating condition |
|
The problem is so small that its solution is immediate and obvious (a base case). |
Compare recursion with a for loop: replace repeated control-variable updates with progressively smaller subproblems, and replace the terminating condition with a base case. section 15.1
Design a recursive function by making each part explicit:
- Define the original problem and the smaller, similar problem passed to the recursive call. section 15.1
- Choose a base case whose answer is immediate, such as a one-element list or an empty tree. section 15.2 section 15.5
- Return the smaller result and combine it with the current step while the calls unwind. section 15.2 section 15.3
- Ensure progress toward the base case; otherwise recursion can become infinite or unexpectedly expensive. section 15.1 section 15.7
Recursive algorithms in practice
Recursion fits problems whose structure repeats: finding the largest value by shortening a list, reversing a list by processing its remainder first, moving disks in Towers of Hanoi, inserting into or traversing a binary search tree, and partitioning sublists in quicksort. Combined with dynamic backtracking, it explores alternative paths in the eight queens and Sudoku puzzles. section 15.2 section 15.4 section 15.5.2 section 15.6
Backtracking extends recursion for search problems. After a path fails, undo its choice and try the next available path. This can find one solution, all solutions, or prove that no solution exists, but brute-force exploration can be costly. section 15.8 section 15.9 section 15.10
