Recursion: Concepts, Tracing and Construction
Explain when recursion is useful, evaluate its limitations, and construct simple non-branching recursive functions in Python.
What you need to be able to do
- explain base cases, recursive cases and progress toward termination;
- trace recursive calls and returned values;
- explain advantages, limitations, complexity and memory implications of recursion;
- connect recursion to suitable applications including fractals, binary trees and sorting;
- construct simple non-branching recursive algorithms in Python.
Rapid Recall Deck
Attempt each card first. If a term is new, flip and study it, then answer it again without looking. Mark only secure recall as “Know it”.
Every recursive solution needs a stopping point
def sum_to(n):
if n == 0:
return 0
return n + sum_to(n - 1)Base case
n == 0 returns a result without another recursive call.
Recursive case
The function reduces n by 1 and calls sum_to() again.
Explain why this terminates for a positive integer n
Each recursive call uses n - 1, so a positive integer moves closer to 0 on every call. When n == 0, the base case returns 0 without making another call. The pending calls can then return their results, so the recursion terminates.
Follow calls down, then returns back up
sum_to(3) using the function from the previous page.Write the call chain and the return chain
sum_to(3) = 3 + sum_to(2) = 3 + 2 + sum_to(1) = 3 + 2 + 1 + sum_to(0) = 3 + 2 + 1 + 0 = 6
Write simple non-branching recursion
Construct factorial(n)
Assume n is a non-negative integer. Return 1 when n == 0; otherwise return n × factorial(n - 1).
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)Recursion trades clarity for call overhead
Explain one trade-off
An iterative loop and a recursive function both correctly calculate a countdown from n to 0. Explain why the recursive version may use more memory even if both perform a similar number of steps.
The recursive version creates a new function call for each smaller value of n. Those calls remain on the call stack until the base case is reached and the calls unwind, so additional stack memory is required. A simple iterative loop can usually update a small fixed set of variables without storing a chain of pending calls.
Use recursion where the problem repeats its own shape
Fractal image creation
A shape can contain smaller versions of the same shape, so the drawing rule can be applied recursively.
Binary-tree traversal
A tree contains subtrees with the same structural idea, making recursive traversal a natural conceptual fit.
Sorting algorithms
Algorithms such as quicksort can solve smaller partitions recursively.
Explain suitability
Why is a recursively defined fractal a natural application of recursion?
A fractal is built from smaller regions that follow the same or a similar generation rule as the whole. A recursive function can apply the rule to a smaller scale on each call until a base condition such as minimum size or depth is reached.
Teacher-created Paper 2 practice
1. Using factorial(0) = 1 and factorial(n) = n × factorial(n-1) for n > 0, trace the return value of factorial(4).
2. Explain why a recursive function needs both a base case and progress toward that base case.
3. Construct countdown(n) so it prints n, recursively calls itself with n - 1, and stops after printing 0. Assume n is non-negative.
4 × 3 × 2 × 1 × 1 = 24.- The base case stops further calls; progress ensures the arguments eventually reach that stopping condition. Missing either can lead to non-termination until the call stack limit is reached.
def countdown(n): print(n) if n == 0: return countdown(n - 1)
Finish the learning cycle
IA — main task
Review any IA problem that has a naturally repeated or hierarchical structure. Only consider recursion if it genuinely improves the solution; do not add it simply to appear advanced.
Syllabus — short retrieval
Redo factorial(4) and the countdown construct without Reveal. Then explain aloud why tree traversal can be recursive even though today's construction practice is non-branching.