Recursion

A function can call itself. Each call gets its own frame, so the frames stack up until a base case stops it:

def countdown(n):
    if n == 0:        # base case
        return
    countdown(n - 1)  # smaller problem

factorial: 5! = 5 × 4 × 3 × 2 × 1, which is 5 × 4!.

Step through factorial(4): four factorial() boxes pile up (n = 4, 3, 2, 1), then unwind, returning 1, 2, 6 and finally 24.

See it run

def total_to(n):
    if n == 0:
        return 0
    return n + total_to(n - 1)

print(total_to(3))

Count the total_to() boxes as they pile up, then watch them unwind.

Practice recursion

Exercise 1

Write a recursive factorial(n): return 1 when n <= 1, otherwise n * factorial(n - 1).

Exercise 2

Write recursive sum_to(n) for nonnegative integers: the sum from 1 through n, with sum_to(0) = 0. Store sum_to(5) in weekly_total.

Exercise 3

Write recursive countdown_labels(n) returning a list of strings from n down to "1" followed by "Go!". For n <= 0, return just ["Go!"]. Each call must return a fresh list.

Exercise 4

Predict, then verify. Read this program before running it:

def total_to(n):
    if n == 0:
        return 0
    return n + total_to(n - 1)

answer = total_to(3)

At the deepest moment, how many total_to() boxes are stacked? And which value is returned first? Guess, then run it, press Step through your code, and press Next until the boxes stop piling up. Set deepest and first_return.

The explanation and tasks are public. Running this lesson requires an account with course access.

Practice

Loading Python…

Loading exercise content…

Visualizer Watch your code run line by line

Run your code, then choose Play to follow its execution.

Memory · names → values

Variables appear here as Python creates them.

Output & plots