A. Programming Concepts and Skills · Algorithm Design and AnalysisThinking Recursively: Base Cases and the Call Stack
A3.6 C2.4 C2.1About 70 minutes
Learning goals- I can identify the base case and the recursive case of a recursive algorithm.
- I can trace a recursive function with the call stack, showing how calls wind up and unwind.
- I can write simple recursive functions: factorial, sum of a list, power, string reversal.
- I can design an efficient recursion (such as fast power) and compare it with iteration.
Words to know
recursion
Solving a problem by having a function call itself on a smaller version of the same problem.
base case
A case simple enough to answer directly, without another recursive call; it stops the recursion.
recursive case
The case where the function calls itself on a smaller input and uses that result.
call stack
The stack of active function calls; each call gets a frame with its own parameters and local variables.
stack frame
The memory for one function call: its parameters, local variables and where to return to.
recursion depth
How many calls are on the stack at once; Python's default limit is about 1000.
How many people are in line?
You are in a long line for skates at the outdoor rink and cannot see the front. You ask the person ahead of you, "How many people are in front of you?" They do not know either, so they ask the person ahead of them, and so on. The person at the very front says "Zero!" Then the answers come back down the line: 1, 2, 3, … until someone tells you, and you add 1.
Nobody counted the whole line, yet everyone got the right answer. Each person solved a smaller version of the same problem, and one person (the front) knew the answer directly. That is recursion. In MCR3U (Sequences and Series) you wrote recursion formulas like tₙ = tₙ₋₁ + 3 with t₁ = 2; now you will write recursive algorithms.
The two parts of every recursive function
- Base case: an input so simple you answer it directly. (The person at the front: "zero".)
- Recursive case: reduce the problem to a smaller one of the same kind, call the function on it, and use the answer. (Ask the person ahead, then add 1.)
The recursive case must always move toward the base case. If it does not, the calls never stop (the topic of Recursion Pitfalls: Infinite Recursion and Exponential Growth).
The classic first example is the factorial: n! = 1 × 2 × 3 × … × n, and 0! = 1. Notice that 4! = 4 × 3!. In general n! = n × (n − 1)!, which is a recursive definition.
def factorial(n):
"""Return n! = 1 x 2 x ... x n.
Precondition: n is an integer >= 0."""
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive case: a smaller problem
print(factorial(4), factorial(0), factorial(10))
Output: 24 1 3628800. The precondition matters: with a negative n, the calls would never reach 0.
What really happens: the call stack
Every time a function is called, Python creates a stack frame holding that call's parameters and local variables, and pushes it on the call stack. When the call returns, its frame is popped off and its value is handed back to the caller.
So factorial(4) does not finish right away. It needs factorial(3), which needs factorial(2), and so on. There are five separate frames at the deepest point, each with its own n. This is the winding phase. When factorial(0) returns 1, the frames finish one by one in reverse order: the unwinding phase.
def factorial(n, depth=0):
indent = " " * depth
print(indent + "factorial(" + str(n) + ") called")
if n == 0:
print(indent + "base case: return 1")
return 1
result = n * factorial(n - 1, depth + 1)
print(indent + "factorial(" + str(n) + ") returns " + str(result))
return result
factorial(3)
Its checked output is shown in the next box. Indenting by call depth makes the stack visible. Each factorial(n) call prints when it starts and when it returns; the deeper calls finish first.
factorial(3) called
factorial(2) called
factorial(1) called
factorial(0) called
base case: return 1
factorial(1) returns 1
factorial(2) returns 2
factorial(3) returns 6
Output of the program above (checked by running it).
Designing a recursive function: three questions
- What is the smallest input, and what is its answer? (Empty list, 0, a string of length 0 or 1.)
- How do I make the problem smaller? (n − 1; the list without its first element; the string without its ends; half the input.)
- If a call on the smaller problem gives me the right answer, how do I build my answer from it?
Question 3 is the "leap of faith": you do not trace every call in your head; you trust the smaller call, exactly as the person in line trusted the answer from ahead. If the base case is right and each step is right, the whole recursion is right. (This is the same reasoning as mathematical induction, which you will meet in university math.)
def total(a):
"""Return the sum of the numbers in list a (recursively)."""
if len(a) == 0: # smallest input: empty list
return 0
return a[0] + total(a[1:]) # first element + sum of the rest
def reverse(s):
"""Return the string s reversed."""
if len(s) <= 1: # "" or one character
return s
return reverse(s[1:]) + s[0] # reverse the rest, then put the first last
def is_palindrome(s):
"""True if s reads the same forwards and backwards."""
if len(s) <= 1:
return True
if s[0] != s[-1]:
return False
return is_palindrome(s[1:-1]) # check the inside
print(total([3, 1, 4, 1, 5]), reverse("Oshawa"), is_palindrome("racecar"), is_palindrome("canoe"))
Output: 14 awahsO True False. Each function answers the three questions. (The slices a[1:] and s[1:-1] copy part of the list or string, which costs extra time; the next lessons show how to avoid that with index parameters.)
Simple and efficient recursion
A3.6 asks for recursive algorithms that are simple and efficient. Compare two ways to compute xⁿ:
power: xⁿ = x × xⁿ⁻¹. It makes n + 1 calls: O(n).fast_power: if n is even, xⁿ = (x^(n/2))²; if n is odd, xⁿ = (x^(n//2))² × x. Each call halves n, so it makes only about log₂ n + 2 calls: O(log n).
The key is to compute fast_power(x, n // 2) once, store it in half, and use it twice. Writing fast_power(x, n // 2) * fast_power(x, n // 2) would make two calls at every level and throw the advantage away (you will see why in Recursion Pitfalls: Infinite Recursion and Exponential Growth).
def power(x, n):
"""x to the power n, for an integer n >= 0. Makes n recursive calls."""
if n == 0:
return 1
return x * power(x, n - 1)
def fast_power(x, n):
"""x to the power n, for an integer n >= 0. Halves n each call."""
if n == 0:
return 1
half = fast_power(x, n // 2) # one recursive call, used twice
if n % 2 == 0:
return half * half
return half * half * x
print(power(2, 10), fast_power(2, 10), fast_power(3, 5))
Output: 1024 1024 243. Both give 2¹⁰ = 1024, and fast_power(3, 5) = 243. For n = 1000, power needs 1001 nested calls, which goes past Python's default limit of 1000 and raises RecursionError, while fast_power needs just 11.
Worked exampleTracing a recursive function
Trace mystery(5) and say what the function computes.
def mystery(n):
if n <= 1:
return n
return mystery(n // 2) + n % 2
- Winding: mystery(5) needs mystery(2) + 5 % 2 = mystery(2) + 1. mystery(2) needs mystery(1) + 2 % 2 = mystery(1) + 0. mystery(1) is a base case: it returns 1.
- Unwinding: mystery(2) = 1 + 0 = 1. mystery(5) = 1 + 1 = 2.
- What it computes: each call adds the last binary digit (n % 2) and recurses on n with that digit removed (n // 2). So it counts the 1s in the binary form of n. 5 is 101 in binary: two 1s.
- Check: mystery(7) = 3 (111), mystery(8) = 1 (1000). It makes about log₂ n calls: O(log n).
mystery(5) returns 2; the function counts the 1 bits in n's binary representation.
Recursion or a loop?
Anything a loop can do, recursion can do, and the reverse is also true (sometimes with an explicit stack). In Python, a simple loop is usually faster and has no depth limit, so for factorial or summing a list, a loop is the practical choice. Recursion shines when the problem itself is recursive: splitting in halves (merge sort, binary search, fast power), shapes made of smaller copies of themselves (fractals), and nested data (folders inside folders, XML elements inside elements). The next three lessons are about exactly those.
Just for funTo understand recursion, you must first understand recursion.
(The joke only works because it has no base case. Neither will your evening, if you forget yours.)
Hands-on activityNesting boxes and a stack of sticky notes
You need: 4 or 5 boxes or containers that fit inside each other (or nested plastic cups), a small object to hide in the smallest one, a pad of sticky notes, a pen, and a computer with Python.
- Hide the object in the smallest box and nest them all. "Algorithm open(box): if the box holds the object, return it (base case); otherwise, open(the box inside)." Act it out and count the calls.
- Sticky-note call stack. Trace
factorial(4) by hand: each time a call starts, write a sticky note "factorial(n): waiting for factorial(n − 1)" and stick it on top of the previous one. At the base case, write the return value. Then peel the notes off one at a time from the top, writing each return value. The notes you peel off first were the last ones added. - Write recursive functions for:
count_down(n) (prints n down to 1, then "Liftoff!"), count_vowels(s), and maximum(a) (the largest element of a non-empty list). For each, write the three design answers as comments first. - Run
power(2, 1000) and read the error message. Then run fast_power(2, 1000).
What to look for: every function has a base case that is reached for every valid input; the sticky notes come off in the reverse of the order they went on.
Your turn
1Name the base case and the recursive case of factorial.
Base case: n == 0 returns 1. Recursive case: return n × factorial(n − 1).
2Write a recursive function sum_to(n) that returns 1 + 2 + … + n (and 0 for n = 0).
def sum_to(n):
if n == 0:
return 0
return n + sum_to(n - 1)
3How many stack frames for factorial are on the call stack at the deepest point when computing factorial(6)?
7: factorial(6), (5), (4), (3), (2), (1) and (0).
reverse("abc") = reverse("bc") + "a"; reverse("bc") = reverse("c") + "b" = "c" + "b" = "cb". So the result is "cb" + "a" = "cba".
5Why is fast_power O(log n) while power is O(n)?
fast_power halves n on every call, so it reaches 0 after about log₂ n calls; power reduces n by 1 each time, so it needs n calls.
6What error do you get if recursion goes more than about 1000 calls deep in Python?
RecursionError: maximum recursion depth exceeded.
More practice: warm-up
An input answered directly, without another recursive call; it stops the recursion.
3Each recursive call has its own copy of which things?
Its own parameters and local variables (its own stack frame).
4In the winding phase, are calls being made or values being returned?
Calls being made (frames pushed). Values return during unwinding.
5What does total([]) return?
More practice: on your own
1Write count(a, x): the number of times x appears in list a, recursively.
def count(a, x):
if len(a) == 0:
return 0
first = 1 if a[0] == x else 0
return first + count(a[1:], x)
2Predict the output:
def f(n):
if n == 0:
return ""
return f(n - 1) + str(n)
print(f(4))
f(4) = f(3) + "4" = f(2) + "3" + "4" = … = "" + "1" + "2" + "3" + "4". Output: 1234.
3Predict the output:
def g(n):
if n == 0:
return ""
return str(n) + g(n - 1)
print(g(4))
The digit is added before the recursive result, so the output is 4321.
4How many calls does fast_power(5, 16) make, and what are the values of n?
n = 16, 8, 4, 2, 1, 0: 6 calls.
5Write a recursive digit_sum(n) for n ≥ 0 (e.g. digit_sum(4096) = 19).
def digit_sum(n):
if n < 10:
return n
return n % 10 + digit_sum(n // 10)
Challenge
1You wrote Euclid's algorithm with a loop in Algorithms Built on Remainders: Digits, Bases, GCD and Check Digits. Now write a recursive gcd(a, b) using Euclid's rule gcd(a, b) = gcd(b, a % b), with gcd(a, 0) = a. Trace gcd(84, 36). Why does it always stop?
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
gcd(84, 36) → gcd(36, 12) → gcd(12, 0) → 12. It stops because a % b is always smaller than b, so the second argument strictly decreases and must reach 0.
2total(a) uses a[1:], which copies the rest of the list. How many element copies does it make in total for a list of n elements, and what is its Big-O? How could you fix it?
Copies of length n − 1, n − 2, …, 0: about n(n − 1) ÷ 2 element copies, so it is O(n²) even though it makes only n + 1 calls. Fix: pass an index instead of slicing: def total(a, i=0): return 0 if i == len(a) else a[i] + total(a, i + 1), which is O(n).
3Write binary(n) that returns the binary representation of n ≥ 1 as a string, recursively (e.g. binary(6) = "110").
def binary(n):
if n < 2:
return str(n)
return binary(n // 2) + str(n % 2)
binary(6) = binary(3) + "0" = (binary(1) + "1") + "0" = "110". It makes about log₂ n calls.
Quiz
1. What must every correct recursive function have?
2. What does factorial(5) return?
3. During the unwinding phase of factorial(4), which call returns first?
4. Why is fast_power(x, n) more efficient than power(x, n)?
5. What does this return for n = 3?
def h(n): return 0 if n == 0 else 2 + h(n - 1)
6. What happens in Python when recursion goes about 1000 calls deep?
Big idea: A3.6 asks students to design simple and efficient recursive algorithms (the curriculum's first example is calculating a factorial). This lesson builds the core skills: base case, recursive case, the call stack, and the three design questions, and it contrasts an inefficient O(n) recursion with an efficient O(log n) one. The RecursionError and the cost of slicing preview C2.4 (recursion pitfalls).
How to help: Act out the "how many people are in line?" story at the dinner table, or the nested boxes. Ask your teen, "What's the base case? How does each call get smaller?" If they can answer both, they understand the function.
Common difficulties:
- Missing or unreachable base cases (for example, n == 0 when n can be negative or can skip over 0).
- Forgetting to return the result of the recursive call (writing
factorial(n - 1) instead of return n * factorial(n - 1)). - Trying to trace every call mentally instead of trusting the smaller call.
- Thinking all calls share one
n: each call has its own frame.