Anatomy of Recursion
Recursion is when a function solves a problem by calling itself on a smaller version of the same problem.
Every correct recursive function contains two essential parts:
| Part | Role | Example () |
|---|---|---|
| Base Case | Stops recursion by answering a tiny input directly | |
| Recursive Case | Breaks the problem down toward the base case |
Here is the classic code implementation:
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive caseCommon pitfall: Forgetting the base case, or writing a recursive step that fails to shrink the input. Both cause infinite recursion until the call stack overflows in a stack overflow.
The Call Stack and Iteration
Each recursive call waits for the smaller call to finish, stacking up frames: factorial(3) waits for factorial(2), and so on, until resolves and results multiply back up.
Anything recursive can also be written iteratively with a loop, and vice versa. Use the comparison below to choose:
| Approach | Strengths | Weaknesses |
|---|---|---|
| Recursion | Expresses trees and divide-and-conquer clearly | Function call overhead, memory cost on stack |
| Iteration | More memory-efficient for simple repetition | Can obscure naturally recursive data structures |
The choice between them is about clarity and cost, not capability. Every recursive function must have a reachable base case, and each step must make the problem strictly smaller.