B2.4.4–5 · HL · Planned

Recursion and its applications

Follow recursive calls down to a base case and back again, then explore how the same idea supports larger applications.

55 minutes

For this lesson

Class activities ↓ Open Python playground →

Animations: Recursive sum Quicksort · HL application Binary-tree traversal · HL application Fractal tree · HL application

Python · step by step

Recursive sum

Example

Watch calls build up, reach the base case, then return in reverse order.

Select Play or Next line to follow Python execution.

Python implementation

The highlight marks the next line to execute. Values show the state before that line.

1def recursive_sum(n):2    if n == 0:3        return 04    subtotal = recursive_sum(n - 1)5    return n + subtotal

Speed

Execution progress

B2.4.5: a simple non-branching recursive function. Each call makes at most one recursive call. For non-negative n: O(n) time and O(n) auxiliary call-stack space. A loop can use O(1) auxiliary space.

By the end of this lesson

Identify a base case and explain progress towards it.
Construct and trace a simple non-branching recursive function.
Explain recursion in quicksort, tree traversal and fractal drawing.
Account for memory used by active recursive calls.

Work through the lesson

01 · 10 minutes

Predict the result

Use the recursive-sum animation. Predict recursive_sum(4), then step through the Python one line at a time. Explain why recursive_sum(0) stops.

02 · 15 minutes

Follow the call stack

Record n for each active call. Pause at the base case, then predict the values returned as the calls finish.

03 · 15 minutes

Construct and test

Write a simple non-branching recursive function. Test its base case and a small input. Explain how each call gets closer to stopping.

04 · 10 minutes

Explore applications

Use the quicksort, tree traversal and fractal animations to explain smaller subproblems. These branching examples illustrate applications; their full implementation is not required by B2.4.5.

05 · 5 minutes

Compare memory

Compare the recursive sum with a loop. Explain why pending recursive calls require extra memory.

Space complexity: what are we counting?

Auxiliary space means the extra working memory an algorithm needs, beyond the input it has already been given. Think of it as scratch space: counters, a running total, new lists and the memory used by active function calls.

In the summation example on textbook page 361, numbers is the supplied input list. The algorithm keeps a running total in sum and uses a fixed number of extra variables. Whether the list has 10 items or 10,000, it still needs only those few variables: O(1) auxiliary space.

The textbook’s O(n) space statement counts the input list too: storing n items takes memory that grows with n. That is total space, including the input. Both descriptions can be correct; they count different things.

A larger value in sum does not mean we keep more totals. For this classroom analysis, we treat each number as one fixed-size value. Creating a new copy of all n items, or saving every intermediate total, would instead need O(n) auxiliary space.

When explaining an answer, state your convention: “O(1) auxiliary space; O(n) total space including the input list.” Time is a separate question: visiting every item still takes O(n) time.

Before you leave

Exit question

What must be true of both the base case and each recursive call for the function to stop?