Recursion solves a problem by having a function call itself on a smaller but similar problem. The calls stop at a base case, then return results as the call chain unwinds. This can produce simple, elegant solutions, but careless recursion can create serious performance problems. section 15.0 section 15.1
Design a recursive solution by checking these elements:
- Define the original problem and identify a smaller version that the same function can solve. section 15.1
- Choose a base case whose answer is immediate and requires no recursive call. section 15.1
- Ensure every recursive call moves toward the base case; otherwise, recursion can continue indefinitely. section 15.1
- Combine each returned result with the current step as the calls unwind. section 15.2
Finding the largest value
A recursive largest() function compares the first vector element with the largest value returned for the remaining, shorter vector. A single-element vector is the base case; each return completes the comparison for its caller. section 15.2
Towers of Hanoi
Move n−1 disks to a temporary pin, move the largest disk to its destination, then move the n−1 disks onto it. Moving one disk is the base case. section 15.4
Recursion with backtracking
Backtracking extends recursion to explore multiple solution paths. A failed recursive attempt returns to an earlier step, reverses the choice, and tries another path. Eight queens and Sudoku use this strategy. section 15.8 section 15.9 section 15.10
When recursion becomes expensive
The direct recursive Fibonacci definition repeatedly computes the same values. Its call tree grows rapidly, making larger inputs increasingly slow despite the function’s compact definition. section 15.7
