Recursion
The idea the course is built around, and the one most people stall on. A recursive function solves a problem by calling itself on a smaller version. The difficulty is never the code — it is learning to stop tracing and start trusting.
- Write a base case and a recursive case that shrinks the input.
- Apply the recursive leap of faith instead of tracing every level.
- Diagnose infinite recursion.
- Say when recursion beats a loop and when it does not.
Some data has no fixed depth. A folder holds folders that hold folders, with no bound known in advance. No fixed number of nested loops can walk it; recursion handles arbitrary depth with one function.
Parsing HTML and JSON, rendering nested user interfaces, searching a file system, and every compiler ever written. Wherever the data nests without limit, the code recurses.
Early Fortran forbade recursion because each function had one fixed block of memory for its variables. Supporting it required the call stack of Unit 3, which is why the two ideas arrived together.
The two parts
Missing base case: it never stops. Recursive case that does not shrink the input: also never stops.
def factorial(n: int) -> int:
"""Return n!, the product of the integers from 1 to n.
Preconditions: n >= 0
>>> factorial(0)
1
>>> factorial(4)
24
"""
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive case, strictly smallerWhen writing the recursive case, assume the recursive call already works. Do not trace it. Ask only: given a correct answer for the smaller problem, how do I build the answer for this one?
For factorial: assume factorial(n - 1) returns
$(n-1)!$ correctly. Then $n!$ is $n$ times that. Done — no tracing
required.
Following every level by hand works for depth three and collapses at depth ten. The leap of faith is not laziness; it is the only technique that scales. Trace once, early, to convince yourself the mechanism works — then stop doing it.
Diagnosing failures
# 1. no base case
def bad1(n: int) -> int:
return n * bad1(n - 1)
# 2. base case unreachable from some inputs
def bad2(n: int) -> int:
if n == 0:
return 1
return n * bad2(n - 2) # odd n skips straight past 0
# 3. input does not shrink
def bad3(n: int) -> int:
if n == 0:
return 1
return n * bad3(n) # same argument foreverRecursionError after about a
thousand calls — Python's limit, which exists to turn an infinite loop
into an error rather than a crash.Recursion versus iteration
def total_loop(xs: list) -> int:
"""Return the sum of xs, iteratively."""
running = 0
for x in xs:
running = running + x
return running
def total_rec(xs: list) -> int:
"""Return the sum of xs, recursively.
>>> total_rec([1, 2, 3])
6
"""
if xs == []:
return 0
return xs[0] + total_rec(xs[1:])xs[1:] copies the rest of
the list every call — making the recursive version $O(n^2)$ in time and
memory.def depth(obj) -> int:
"""Return the nesting depth of obj, a nested list.
>>> depth(5)
0
>>> depth([1, [2, [3]]])
3
"""
if not isinstance(obj, list):
return 0
if obj == []:
return 1
return 1 + max(depth(item) for item in obj)No loop structure can do this, because the nesting depth is not known when the code is written. Unit 6 develops this pattern properly.
• No base case, or one unreachable from some
inputs.
• A recursive call that does not strictly shrink the
input.
• Tracing every level instead of trusting the call.
• Forgetting to return the recursive call's result.
• Slicing a list on every call and quietly making the function
quadratic.
Practice
Write out each answer before opening it. Original exercises written for this guide in the style of the course's weekly work.
What must every recursive function have?
Answer
Why does bad2 above fail on odd input?
Answer
Write a function printing $n$ down to $1$.
Solution
def countdown(n: int) -> None:
"""Print the integers from n down to 1, one per line.
Preconditions: n >= 0
"""
if n == 0:
return
print(n)
countdown(n - 1)print after the call would count
up instead — the same code, opposite output.Write it recursively and say why it is slow.
Solution
def fib(n: int) -> int:
"""Return the nth Fibonacci number, with fib(0) = 0.
Preconditions: n >= 0
>>> fib(6)
8
"""
if n < 2:
return n
return fib(n - 1) + fib(n - 2)Assuming rev(s[1:]) reverses correctly, write
rev.
Solution
def rev(s: str) -> str:
"""Return s reversed.
>>> rev('abc')
'cba'
"""
if s == '':
return ''
return rev(s[1:]) + s[0]Test a palindrome recursively.
Solution
def is_pal(s: str) -> bool:
"""Return whether s reads the same forwards and backwards.
>>> is_pal('racecar')
True
"""
if len(s) < 2:
return True
return s[0] == s[-1] and is_pal(s[1:-1])Summing a flat list — loop or recursion?
Answer
What does this return, and why?
def f(n: int) -> int:
if n == 0:
return 1
n * f(n - 1)Answer
None for
any $n > 0$. The recursive case computes the value and discards it — the
return is missing. A very common
slip.Expanded topic checklist
Course coverage. This unit is part of the complete CSC148H1 topic map. It should cover the following items before you move on:
- Structure. Base case and recursive case, and what each must guarantee.
- The leap of faith. Trusting the recursive call rather than tracing it.
- Failure modes. Missing, unreachable and non-shrinking cases.
- Judgment. When recursion beats iteration and when it costs more than it gives.
The calendar names "recursion" explicitly. It is the concept the course is organised around and the most heavily assessed; check Quercus for the assigned exercises.
Reduce to a smaller instance, trust the result, combine. Unit 6 applies this to nested data and Units 7 and 8 to trees, where recursion is not a choice but the only reasonable approach.
Deep practice extensions
Use these after the main practice set. They push on definitions and edge cases rather than routine calculation.
What two things must a recursive function have?
Guide
What is the recursive leap of faith?
Guide
Name two causes.
Guide
When does recursion beat a loop?