Anatomy of Recursion
Recursion is a technique where a function calls itself on a smaller version of a problem until it reaches a directly solvable case. It parallels mathematical induction.
Every recursive function requires two core ingredients:
| Ingredient | Role | Example () |
|---|---|---|
| Base case | Stops recursion directly | |
| Recursive case | Shrinks problem & calls self |
To compute , the function descends to the base case, then unwinds upward: .
Rules and Pitfalls
Recursive calls must make strict progress toward the base case. If the subproblem does not shrink, the function recurses forever, triggering a stack overflow as pending calls pile up.
| Property | Requirement |
|---|---|
| Termination | Must reach base case |
| Convergence | Inputs must strictly decrease |
Proving a recursive function correct is an induction. The base case establishes correctness, and the recursive step ensures larger instances build correctly on smaller ones.