Introduction
Recursion is a technique where a function solves a problem by calling itself on smaller instances of the same problem. Every recursive solution needs two essential parts: a base case that stops the recursion, and a recursive case that reduces the problem toward the base case. Without a well-defined base case, a recursive function will call itself indefinitely, eventually exhausting the call stack and causing a stack overflow error.
Cricket analogy: A commentator explaining a record breaks it down recursively -- this is the best since the previous decade's benchmark, which was the best since the one before -- but without a stopping point (a first-ever match base case), the explanation would regress forever.
Explanation
Each call to a recursive function creates a new stack frame that stores its local variables and the point to return to once the call completes. As the function calls itself, frames pile up on the call stack; when the base case is reached, the calls begin returning and the stack unwinds, combining results along the way. This mental model — frames stacking up then unwinding — explains both why recursion works and why it has memory overhead proportional to the depth of recursion. A classic example is computing the factorial of n: factorial(n) = n * factorial(n-1), with the base case factorial(0) = 1.
Cricket analogy: Each unresolved LBW review sent up the chain (umpire to third umpire to ball-tracking check) is like a stack frame holding onto its question until an answer returns, then the decisions unwind back down; factorial-style, each level waits on the level below it to resolve first.
Example
def factorial(n):
# Base case: stops the recursion
if n == 0:
return 1
# Recursive case: reduces the problem size
return n * factorial(n - 1)
def sum_digits(n):
# Base case
if n < 10:
return n
# Recursive case: peel off the last digit
return n % 10 + sum_digits(n // 10)
print(factorial(5)) # 120
print(sum_digits(1234)) # 10Analysis
factorial(5) calls factorial(4), which calls factorial(3), and so on until factorial(0) returns 1. The stack then unwinds, multiplying 1*1, then 2*1, then 3*2, then 4*6, then 5*24, producing 120. This function runs in O(n) time and uses O(n) stack space because there are n nested calls before the base case is hit. Python's default recursion limit (around 1000 frames, configurable via sys.setrecursionlimit) means very deep recursion can hit a RecursionError, which is a practical reason to consider an iterative alternative for large inputs.
Cricket analogy: Tallying a partnership run-by-run -- ball 1 adds to ball 0's total, ball 2 adds to that, and so on -- takes O(n) time and O(n) memory for n balls tracked, and just as a scorer can't track an infinitely long innings, Python hits a RecursionError past roughly 1000 nested calls.
Key Takeaways
- Every recursive function needs a base case (to stop) and a recursive case (to make progress).
- Each recursive call adds a stack frame; the stack unwinds as calls return, combining partial results.
- Recursion uses O(depth) additional memory for the call stack, unlike most iterative loops.
- Forgetting the base case, or failing to move toward it, causes infinite recursion and a stack overflow.
Practice what you learned
1. What are the two essential components of any correct recursive function?
2. What happens if a recursive function has no base case, or the recursive case never reaches it?
3. For factorial(n) implemented recursively as shown, what is the space complexity due to the call stack?
4. In the sum_digits(n) example, what does the recursive case do?
Was this page helpful?
You May Also Like
Recursion Trees and Recurrence Relations
Model the runtime of recursive algorithms as recurrence relations and solve them by drawing recursion trees.
Recursion vs Iteration
Compare recursive and iterative solutions in terms of clarity, performance, memory usage, and when to prefer each.
The Backtracking Paradigm
Learn how backtracking systematically builds candidate solutions and abandons paths that cannot possibly succeed.