A. Programming Concepts and Skills · Algorithm Design and AnalysisRecursion Pitfalls: Infinite Recursion and Exponential Growth
C2.4 A3.6 C2.1About 70 minutes
Learning goals- I can recognize the causes of infinite recursion: a missing, unreachable or skipped base case, or a call that does not make the problem smaller.
- I can explain why naive recursive Fibonacci makes an exponential number of calls, and count them.
- I can fix exponential recursion with memoization or an iterative (bottom-up) algorithm.
- I can spot other hidden costs in recursion: repeated calls, slicing copies and deep call stacks.
Words to know
infinite recursion
Recursion that never reaches a base case; in Python it ends with a RecursionError when the stack limit is hit.
stack overflow
Running out of call-stack space because the recursion is too deep; Python guards against it with a recursion limit.
exponential growth
Work that multiplies by a constant factor each time n increases by 1, such as O(2ⁿ).
overlapping subproblems
When different branches of a recursion solve the same smaller problem again and again.
memoization
Storing the result of each call (for example in a dictionary) so that repeated calls return the stored answer instead of recomputing it.
bottom-up (iterative) solution
Computing the small cases first and building up to n with a loop, instead of recursing down from n.
Two ways recursion goes wrong
Recursion can fail in two very different ways. It can never stop (infinite recursion), which at least crashes loudly. Or it can be correct but hopelessly slow: a five-line function that gives the right answer for n = 30 in a fraction of a second, but would need roughly an hour for n = 50. Curriculum expectation C2.4 asks you to identify these common pitfalls, naming infinite recursion and exponential growth such as the Fibonacci numbers.
Pitfall 1: infinite recursion
Every call must get closer to a base case, and must eventually land on it. Four common ways to break this:
- No base case at all.
def f(n): return n * f(n - 1) never stops. - The base case can be skipped. The function below counts down by 2 and only stops at exactly 0. Starting from an odd number it jumps over 0 and keeps going: 7, 5, 3, 1, −1, −3, …
- The problem does not get smaller. For example
total(a) calling total(a) instead of total(a[1:]), or a binary search calling itself with the same low and high. - A precondition is broken.
factorial(-1) goes −2, −3, … because the base case n == 0 is "behind" it.
In Python, infinite recursion ends with RecursionError: maximum recursion depth exceeded after about 1000 calls. In languages without that check, the program crashes with a stack overflow (the call stack runs out of memory).
def countdown_by_two(n):
if n == 0: # base case: only exactly 0
return "liftoff"
return countdown_by_two(n - 2)
print(countdown_by_two(8))
print(countdown_by_two(7))
8 → 6 → 4 → 2 → 0 works. 7 → 5 → 3 → 1 → −1 → … skips 0, so after the first line is printed the program stops with RecursionError: maximum recursion depth exceeded. The fix is a safer base case, if n <= 0:, or a precondition (n is even and n ≥ 0) that is checked.
Do not just raise the limit
sys.setrecursionlimit(100000) lets Python go deeper, but it does not fix infinite recursion (it just crashes later), and very deep recursion can crash the whole Python process. If a correct algorithm needs recursion thousands of levels deep (like summing a long list one element at a time), use a loop instead, or a recursion that halves the problem so the depth is only log₂ n.
Pitfall 2: exponential growth (Fibonacci)
The Fibonacci sequence (from MCR3U, Sequences and Series) is 0, 1, 1, 2, 3, 5, 8, 13, …, where each term is the sum of the two before it. With fib(0) = 0 and fib(1) = 1, the definition turns directly into code. It is correct, and it is a trap.
calls = 0
def fib(n):
"""Return the nth Fibonacci number: fib(0) = 0, fib(1) = 1."""
global calls
calls += 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
for n in [5, 10, 15, 20, 25, 30]:
calls = 0
value = fib(n)
print("fib(" + str(n) + ") =", value, "calls:", calls)
Output, one line each: fib(5) = 5 calls: 15, fib(10) = 55 calls: 177, fib(15) = 610 calls: 1973, fib(20) = 6765 calls: 21891, fib(25) = 75025 calls: 242785, fib(30) = 832040 calls: 2692537. A global counter counts every call. On one computer the whole program ran in about 0.2 seconds, almost all of it on fib(30).
Why does the number of calls explode?
Each call to fib(n) makes a call to fib(n − 1) and to fib(n − 2). Let C(n) be the number of calls. Then C(0) = C(1) = 1 and C(n) = 1 + C(n − 1) + C(n − 2). This grows like the Fibonacci numbers themselves: in fact C(n) = 2 × fib(n + 1) − 1. Check: C(5) = 2 × 8 − 1 = 15.
Fibonacci numbers grow by a factor of about 1.618 (the golden ratio) each step, so every increase of n by 5 multiplies the work by about 11 (1.618⁵ ≈ 11.1). That is exponential growth, roughly O(1.618ⁿ), and it is often written loosely as O(2ⁿ).
- fib(30): about 2.7 million calls (a fraction of a second).
- fib(40): about 330 million calls (tens of seconds in Python).
- fib(50): about 40 billion calls (most of an hour).
- fib(100): about 1.1 × 10²¹ calls: far longer than you will live.
The cause is overlapping subproblems: the two branches of the call tree recompute the same values. Only n + 1 different values (fib(0) to fib(n)) are ever needed.
The fixes: remember, or build up
- Memoization: keep a dictionary of answers already computed. Before computing fib(n), check the dictionary. Each value is now computed once: O(n) time, at the cost of O(n) memory. (Python's
functools.lru_cache decorator does this automatically.) - Bottom-up iteration: start from fib(0) and fib(1) and build upward with a loop, keeping only the last two values. O(n) time, O(1) memory, and no recursion depth problem at all.
memo = {0: 0, 1: 1} # answers we already know
def fib_memo(n):
"""Fibonacci with memoization: each fib(k) is computed only once."""
if n not in memo:
memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
return memo[n]
def fib_loop(n):
"""Fibonacci bottom-up: no recursion at all, O(n) time, O(1) memory."""
a, b = 0, 1 # fib(0), fib(1)
for i in range(n):
a, b = b, a + b
return a
print(fib_memo(30), fib_loop(30))
print(fib_memo(90))
print(fib_loop(300) == fib_memo(300))
Output, one line each: 832040 832040, 2880067194370816120, True. Both fixes give fib(30) = 832040 instantly, and fib(90) (a 19-digit number) as well. The naive version would need about 9 × 10¹⁸ calls for fib(90).
Worked exampleSpot the hidden exponential
A student "simplifies" fast power from Thinking Recursively: Base Cases and the Call Stack:
def fast_power(x, n):
if n == 0:
return 1
if n % 2 == 0:
return fast_power(x, n // 2) * fast_power(x, n // 2)
return fast_power(x, n // 2) * fast_power(x, n // 2) * x
It still gives correct answers. How many calls does it make for n = 16, and what is its Big-O?
- Each call (with n ≥ 1) now makes two recursive calls on n // 2 instead of one.
- For n = 16 the levels are n = 16, 8, 4, 2, 1, 0 with 1, 2, 4, 8, 16, 32 calls: 1 + 2 + 4 + 8 + 16 + 32 = 63 calls (the original version makes 6).
- The depth is about log₂ n, and the number of calls doubles at each level, so there are about 2^(log₂ n + 2) ≈ 4n calls (exactly 4n − 1 = 63 when n = 16 is a power of 2): O(n). The efficient O(log n) algorithm has become no better than the simple loop.
- Fix: compute
half = fast_power(x, n // 2) once and reuse it. The general lesson: when two recursive calls have the same arguments, compute it once (or memoize).
63 calls for n = 16, O(n) instead of O(log n). Two identical calls per level double the work at every level.
Other hidden costs
- Slicing in every call:
total(a[1:]) copies the rest of the list each time, so a "linear" recursion does about n² ÷ 2 element copies: O(n²). Pass an index (or low and high) instead. - Depth: a recursion that reduces n by 1 needs n stack frames. Fine for n = 100, a RecursionError for n = 5000. Halving recursions (binary search, merge sort, fast power) have depth about log₂ n, which is always safe.
- Memoization's own depth:
fib_memo(5000) called from scratch still recurses about 5000 deep before the dictionary fills up, so with Python's default limit it raises RecursionError. The bottom-up loop has no such problem.
Checklist for any recursive function: Does every input reach a base case? Does every call make the problem strictly smaller? How many calls does each call make, and do they repeat work? How deep can it go?
Just for funFibonacci's rabbits (from his 1202 book Liber Abaci) would have had no trouble with naive recursion. They just multiplied.
The computer, on the other hand, would like a word with them about fib(50).
Hands-on activityWatch it explode, then fix it
You need: a computer with Python, and paper for a table.
- Run the call-counting program. Add n = 32 and 34. Make a table of n, calls, and calls ÷ previous calls. What ratio do you see? (About 1.618² ≈ 2.6 for steps of 2.)
- Time fib(25), fib(30) and fib(32) with
time.perf_counter(). Predict fib(40)'s time from the pattern before you try it (be ready to stop it with Ctrl+C). - Draw the call tree for fib(6) on paper. Circle every repeated subproblem. Count the calls (should be 25 = 2 × fib(7) − 1 = 2 × 13 − 1).
- Add a counter to
fib_memo (start with an empty memo each time, except for the base cases). How many calls for n = 30? (Should be 2n − 1 = 59.) - Write
countdown_by_two with a fixed base case and an assert that checks the precondition. Try it on 7.
What to look for: the naive call counts grow by about 1.6 per step; memo calls grow by 2 per step; your prediction for fib(40) should be roughly 100 times the fib(30) time (1.618¹⁰ ≈ 123).
Your turn
1Give three different causes of infinite recursion.
Any three: no base case; a base case that can be skipped (e.g. n == 0 when n goes down by 2); the recursive call is not on a smaller input; a broken precondition (e.g. negative n for factorial).
2Fix this function so it works for every integer n ≥ 0:
def evens(n): return 0 if n == 0 else n + evens(n - 2)
Use if n <= 0: return 0 (or handle n == 1 too). For odd n the original skips 0. With n <= 0 the base case catches both 0 and −1.
3How many calls does naive fib(6) make?
2 × fib(7) − 1 = 2 × 13 − 1 = 25.
4Why is naive recursive Fibonacci exponential?
Each call makes two more calls, and the branches recompute the same subproblems (overlapping subproblems), so the number of calls grows by about 1.618 each time n increases by 1.
5Explain memoization in one or two sentences.
Store each answer the first time it is computed (e.g. in a dictionary), and return the stored answer for any later call with the same input, so each subproblem is solved only once.
6What is the time and extra memory of fib_loop(n)?
O(n) time and O(1) extra memory (just two variables).
More practice: warm-up
1What error does Python raise for infinite recursion?
RecursionError (maximum recursion depth exceeded).
0, 1, 1, 2, 3, 5, 8, 13, 21.
3What are overlapping subproblems?
The same smaller problem being solved repeatedly in different branches of a recursion.
4Is raising the recursion limit a fix for infinite recursion?
No: it only delays the crash.
5What does a bottom-up solution do?
Computes the small cases first and builds up to n with a loop.
More practice: on your own
1How many calls does fib(4) make? List them.
fib(4) → fib(3), fib(2); fib(3) → fib(2), fib(1); each fib(2) → fib(1), fib(0). Calls: fib(4), fib(3), fib(2), fib(1), fib(0), fib(1), fib(2), fib(1), fib(0) = 9 (= 2 × fib(5) − 1 = 9).
2Naive fib(30) took 0.2 s. Estimate the time for fib(35) and fib(45).
Each +5 multiplies the work by about 11: fib(35) ≈ 0.2 × 11 ≈ 2 s; fib(45) ≈ 0.2 × 11³ ≈ 270 s (about 4.5 minutes).
3This function is meant to sum a list but never stops. Find the bug:
def total(a, i):
if i == len(a):
return 0
return a[i] + total(a, i)
The recursive call passes the same i, so the problem never gets smaller. It should be total(a, i + 1).
4Write a memoized function for the number of ways to climb n stairs taking 1 or 2 steps at a time (ways(0) = 1, ways(1) = 1, ways(n) = ways(n − 1) + ways(n − 2)). What is ways(10)?
known = {0: 1, 1: 1}
def ways(n):
if n not in known:
known[n] = ways(n - 1) + ways(n - 2)
return known[n]
ways(10) = 89 (it is fib(11)).
5Why is the depth of binary search's recursion never a problem, but the depth of total(a, i) can be?
Binary search halves the range, so its depth is about log₂ n (about 30 for a billion elements). total reduces by 1, so its depth is n, which exceeds Python's limit for n ≈ 1000.
Challenge
1Prove that C(n) = 2 × fib(n + 1) − 1, where C(n) = 1 + C(n − 1) + C(n − 2), C(0) = C(1) = 1.
Check the base cases: C(0) = 2 × fib(1) − 1 = 1 ✓ and C(1) = 2 × fib(2) − 1 = 1 ✓. Inductive step: if it holds for n − 1 and n − 2, then C(n) = 1 + (2 fib(n) − 1) + (2 fib(n − 1) − 1) = 2(fib(n) + fib(n − 1)) − 1 = 2 fib(n + 1) − 1 ✓.
2Pascal's triangle entries satisfy C(n, k) = C(n − 1, k − 1) + C(n − 1, k), with C(n, 0) = C(n, n) = 1. Is the naive recursion exponential? How would you make it efficient?
Yes: like Fibonacci, each call makes two calls and the subproblems overlap heavily (C(n − 2, k − 1) is reached from both branches), so the naive version makes about 2 × C(n, k) − 1 calls, which is exponential for k near n ÷ 2. Fix: memoize on the pair (n, k), or build the triangle row by row bottom-up: O(n × k) time.
3The Ackermann function A(m, n) always terminates, yet A(4, 2) has 19 729 digits. What does this tell you about checking a recursion for "infinite recursion" versus "too slow"?
A recursion can be guaranteed to reach its base case (it terminates) and still be completely impractical. Termination and efficiency are separate questions: first check that every call makes progress toward a base case, then count the calls (or the growth rate) to decide whether it is usable.
Quiz
1. Why does def f(n): return 1 if n == 0 else f(n - 2) fail for f(5)?
2. How many calls does naive recursive fib(7) make?
3. What is the main cause of naive Fibonacci's slowness?
4. What is the time complexity of Fibonacci with memoization?
5. Which change turns an efficient O(log n) recursion into an O(n) one?
6. A correct recursive function reduces n by 1 per call. What problem appears for n = 10 000 in Python?
Big idea: C2.4 asks students to identify common pitfalls in recursive functions, naming infinite recursion and exponential growth such as the Fibonacci numbers. This lesson diagnoses both, counts the exponential calls exactly, and shows the standard fixes (memoization and bottom-up iteration), which are the foundation of "dynamic programming" in university courses. It also revisits efficient recursive design (A3.6) and preconditions (C2.1).
How to help: Draw the fib(5) call tree together and count the repeats. Then ask, "How would you compute the 50th Fibonacci number by hand?" (You would list them from the start, which is the bottom-up solution.)
Common difficulties:
- Believing a recursion is fine because it gives the right answer for small n.
- Base cases that only work for some inputs (even but not odd, positive but not zero).
- Thinking
sys.setrecursionlimit is a fix. - Memoizing with a dictionary that is accidentally reset inside the function on every call.