Chapter 3 · Data
Recursion
Step 1 of 20 · Concept
A function can call itself
In this lesson you write functions that call themselves, and watch their frames pile up.
def countdown(n):
if n == 0:
return
print(n)
countdown(n - 1)
A function that calls itself is recursion. Each call has a smaller n. The base case, n == 0, stops
it: return alone ends the call at once.
Step 2 of 20 · Quiz
Predict the countdown
Type exactly what this program prints.
def countdown(n):
if n == 0:
return
print(n)
countdown(n - 1)
countdown(3)
print("Go")
Step 3 of 20 · Demo
See it run
Run it and compare with your answer. Then change countdown(3) to countdown(5).
Step 4 of 20 · Concept
A smaller copy of the same problem
The factorial of 3 is 3 * 2 * 1, which is 6. It is 3 times the factorial of 2, a smaller copy of the same
problem.
def fact(n):
if n == 1:
return 1
return n * fact(n - 1)
- The base case:
fact(1)is 1, with no call. - Every other
fact(n)isn * fact(n - 1). It waits for the smaller call's answer, then multiplies.
Step 5 of 20 · Trace
Frames pile up, then return
Each call gets its own frame, with its own n (lesson 7). Press Next and watch the stack grow and shrink.
def fact(n):
if n == 1:
return 1
return n * fact(n - 1)
print(fact(3))- Line 7 called
fact(3): a frame withn3 sits on the<module>frame. Line 2 asks ifnis 1. - 3 is not 1, so line 4 called
fact(2). A new frame, with its ownn, sits on top. - 2 is not 1 either:
fact(1)gets a frame. The calls under it wait for their answers. - Now
nis 1: the base case. Line 3 returns 1 without a call. fact(1)returned 1, and its frame is gone.fact(2)finishes line 4:2 * 1.fact(2)returned 2.fact(3)finishes line 4:3 * 2.fact(3)returned 6, and its frame is gone. Line 7 prints it.- Line 7 printed
6. The program is finished, and the stack is empty.
Step 6 of 20 · Quiz
How deep does it go?
While print(fact(3)) runs, what is the most fact frames on the stack at once?
def fact(n):
if n == 1:
return 1
return n * fact(n - 1)
print(fact(3))Step 7 of 20 · Exercise
Your turn: sum of digits
Write sum_digits(n) with recursion: it adds up the digits of n, for any n of 0 or more.
n % 10is the last digit ofn, andn // 10isnwithout it (lesson 3).- So the sum for 2026 is 6 plus the sum for 202.
The output must be exactly:
7 6
10 45
Which numbers can you add up with no smaller call?
The base case: when n < 10, return n. Otherwise, return the last digit plus the sum for the rest.
return n % 10 + sum_digits(n // 10)
Step 8 of 20 · Concept
No base case: RecursionError
def countdown(n):
countdown(n - 1)
countdown(3)
Without a base case, the calls never stop by themselves. Python stops them at about 1000 frames, with a
RecursionError. The traceback folds the repeats into one line:
Traceback (most recent call last):
File "main.py", line 5, in <module>
countdown(3)
~~~~~~~~~^^^
File "main.py", line 2, in countdown
countdown(n - 1)
~~~~~~~~~^^^^^^^
File "main.py", line 2, in countdown
countdown(n - 1)
~~~~~~~~~^^^^^^^
File "main.py", line 2, in countdown
countdown(n - 1)
~~~~~~~~~^^^^^^^
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
Step 9 of 20 · Demo
Watch it stop
sys.setrecursionlimit(50) lowers the limit to 50 frames, so it stops sooner. Run it, and read the traceback from
its last line, as in lesson 5.
Step 10 of 20 · Quiz
Why did it stop?
Why did this program stop with a RecursionError?
import sys
sys.setrecursionlimit(50)
def countdown(n):
countdown(n - 1)
countdown(3)Step 11 of 20 · Try it
Try it: add the base case
Run it: it prints from 3 into negative numbers, then stops with a RecursionError. Add the base case, so that it
prints 3, 2, 1 and Go.
The base case goes first in the function: when n is 0, return before it prints.
Step 12 of 20 · Concept
Two calls: fibonacci
The Fibonacci numbers start 0, 1. Each next one is the sum of the two before: 0, 1, 1, 2, 3, 5, 8.
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
Each call makes two calls, so the work multiplies: fib(35) takes almost 30 million calls.
Step 13 of 20 · Demo
The first ten
Run it. fib_loop gets the same numbers with a loop of two names: fast, even for fib_loop(80).
Step 14 of 20 · Concept
Lists inside lists
isinstance(x, list) is True when x is a list. The sum of [1, [2, 3], [4, [5]]]:
def nested_sum(items):
total = 0
for x in items:
if isinstance(x, list):
total += nested_sum(x)
else:
total += x
return total
print(nested_sum([1, [2, 3], [4, [5]]]))
An item that is a list is a smaller copy of the problem.
Step 15 of 20 · Quiz
Predict the sum
Type exactly what this program prints.
def nested_sum(items):
total = 0
for x in items:
if isinstance(x, list):
total += nested_sum(x)
else:
total += x
return total
print(isinstance(5, list))
print(isinstance([5], list))
print(nested_sum([1, [2, 3], [4, [5]]]))Step 16 of 20 · Demo
See it run
Run it and compare with your answer.
Step 17 of 20 · Exercise
Your turn: flatten
Write flatten(items) with recursion: it returns one flat list of all the numbers, in order. The output must be
exactly:
[1, 2, 3, 4, 5]
[7, 8]
It has the shape of nested_sum, with an empty list where nested_sum has 0.
A number: append it. A list: flatten it, and add its numbers to yours with += (lesson 10).
if isinstance(x, list):
flat += flatten(x)
Step 18 of 20 · Check yourself
Check yourself: power and palindrome
Write both functions with recursion.
power(b, e)multipliesecopies ofbtogether;power(b, 0)is 1.is_palindrome(s)isTruewhensreads the same both ways.s[1:-1]isswithout its first and last characters.
The output must be exactly:
1024 81
True False
True True
power has the shape of fact. A text of fewer than 2 characters is a palindrome; a longer one needs equal ends.
Step 19 of 20 · Challenge · optional
Challenge: fast fibonacci
Optional. Keeping each answer so that you never work it out twice is called memoisation.
Make fib remember its answers in the dictionary memo, then add print(fib(80)). Without memo, fib(80)
would take years: press Stop if it hangs. The output must be exactly:
610
23416728348467685
In the tree of fib(4), fib(2) is worked out twice. Work out each fib(n) once, and keep its answer.
Before the work, if n in memo, return memo[n]. After it, put the answer in memo[n], then return it.
memo[n] = ... changes the dictionary; it does not give the name memo a new value, so memo stays the
<module> frame's (lesson 7).
memo[n] = fib(n - 1) + fib(n - 2)
Step 20 of 20 · Recap
Recap
- A recursive function calls itself on a smaller problem. Its base case answers without a call.
- Each call gets its own frame. The frames pile up, then go newest first.
- Without a base case, Python stops at about 1000 frames with a
RecursionError. - Two calls each time multiply the work: a loop is faster.
isinstance(x, list)tells a list inside a list from a number.
Next: lesson 15 makes new kinds of value: classes and objects.
Review
4 questions from this lesson, in a new order each time. Answer from memory: 3 of 4 right on the first try passes. On a day after you finish the lesson, a pass earns 15 XP.
The review needs JavaScript.
def countdown(n):
if n == 0:
return
print(n)
countdown(n - 1)
countdown(3)
print("Go")
def sum_digits(n):
# the base case first, then a smaller call
return 0
print(sum_digits(7), sum_digits(123))
print(sum_digits(2026), sum_digits(99999))
import sys
sys.setrecursionlimit(50)
def countdown(n):
countdown(n - 1)
countdown(3)
import sys
sys.setrecursionlimit(50)
def countdown(n):
print(n)
countdown(n - 1)
countdown(3)
print("Go")
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
def fib_loop(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
print([fib(n) for n in range(10)])
print(fib_loop(9), fib_loop(80))
def nested_sum(items):
total = 0
for x in items:
if isinstance(x, list):
total += nested_sum(x)
else:
total += x
return total
print(isinstance(5, list))
print(isinstance([5], list))
print(nested_sum([1, [2, 3], [4, [5]]]))
def flatten(items):
# return one list of all the numbers in items
return []
print(flatten([1, [2, 3], [4, [5]]]))
print(flatten([[[7]], 8]))
def power(b, e):
return 0
def is_palindrome(s):
return False
print(power(2, 10), power(3, 4))
print(is_palindrome("level"), is_palindrome("abca"))
print(is_palindrome("noon"), is_palindrome(""))
memo = {}
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(15))