Unit 30: Recursion Deeper
Problems inside problems.
Unit 30 of 31 in Python for kids. Its 6 lessons are The Recursive Recipe, When Recursion Explodes, Towers of Hanoi, Every Possibility, Backtracking and Recursion Master — below is everything each one explains, and a question or two from it to try.
Every sample on this page was run through real Python before it shipped, and prints exactly what it says it prints.
This unit opens with a fortnight’s trial of everything — no card needed — or with a family plan, bought in the iPhone app. The first two units of every track are free for ever. Try it in the app.
🪆 The Recursive Recipe
Two questions, every time
Every recursive function answers the same two questions: when is it too small to bother? and how do I make it smaller? Get those right and the rest follows.
Python
def power(base, n):
if n == 0:
return 1
return base * power(base, n - 1)
print(power(2, 10))
print(power(5, 3))It prints
1024 125
Text works the same way
Reversing a word is the last letter, followed by the reverse of everything else. The base case is the empty string.
Python
def reverse(text):
if text == "":
return ""
return text[-1] + reverse(text[:-1])
print(reverse("hello"))It prints
olleh
Euclid’s trick, 2000 years old
The biggest number that divides both a and b also divides the remainder of a divided by b. So keep replacing the pair with the smaller one until nothing is left over.
Python
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
print(gcd(48, 18))
print(gcd(100, 75))It prints
6 25
Try it yourself
What happens if the recursive call does not make the problem smaller?
- Python fixes it
- It calls itself for ever until Python gives up
- It returns None
- It runs once
What does this print?
Python
def count_down(n):
if n == 0:
return "go"
return str(n) + " " + count_down(n - 1)
print(count_down(3))Answer them in the app
💥 When Recursion Explodes
Two calls instead of one
Fibonacci looks harmless — each number is the sum of the two before it. But each call makes two more, so the work doubles at every level.
Python
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(10))
print(fib(20))It prints
55 6765
Count the calls and it is alarming
Ten needs 177 calls. Twenty needs nearly twenty-two thousand. Every extra number roughly *doubles* the work.
Python
calls = 0
def fib(n):
global calls
calls = calls + 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
calls = 0
fib(10)
print(calls)
calls = 0
fib(20)
print(calls)It prints
177 21891
It keeps solving the same thing
This is the reason. Working out fib(5) computes fib(3) twice, fib(2) three times, and so on — the same answers over and over, from scratch each time.
Python
counts = {}
def fib(n):
counts[n] = counts.get(n, 0) + 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
fib(6)
for n in sorted(counts):
print(n, "worked out", counts[n], "times")It prints
0 worked out 5 times 1 worked out 8 times 2 worked out 5 times 3 worked out 3 times 4 worked out 2 times 5 worked out 1 times 6 worked out 1 times
Try it yourself
Why is naive Fibonacci so slow?
- Recursion is always slow
- It solves the same smaller problems again and again instead of remembering them
- The numbers get too big
- It uses too much memory
Which of these does NOT have this problem?
- Naive Fibonacci
- Counting down from n, which makes only one call each time
- Any recursion
- Towers of Hanoi
Answer them in the app
🗼 Towers of Hanoi
The puzzle
Move a stack of discs from one peg to another. Only one disc at a time, and a bigger disc may never sit on a smaller one. It looks impossible until you think recursively.
Python
print("to move 3 discs from A to C:")
print(" move 2 discs out of the way to B")
print(" move the big one A -> C")
print(" move the 2 discs from B onto C")It prints
to move 3 discs from A to C: move 2 discs out of the way to B move the big one A -> C move the 2 discs from B onto C
That description is the code
Three lines, and each one is exactly a line of the plan above. The base case is having no discs to move.
Python
def hanoi(n, source, spare, target):
if n == 0:
return
hanoi(n - 1, source, target, spare)
print(source, "->", target)
hanoi(n - 1, spare, source, target)
hanoi(2, "A", "B", "C")It prints
A -> B A -> C B -> C
Three discs, seven moves
Each extra disc roughly doubles the moves: 1, 3, 7, 15, 31. For n discs it is always 2 to the power n, minus 1.
Python
def count_moves(n):
if n == 0:
return 0
return count_moves(n - 1) + 1 + count_moves(n - 1)
for discs in [1, 2, 3, 4, 5]:
print(discs, count_moves(discs))It prints
1 1 2 3 3 7 4 15 5 31
Try it yourself
The legend says 64 golden discs. Why will the world not end soon?
- The discs are too heavy
- 2 to the power 64 is about 18 quintillion moves
- Nobody knows the rules
- It would only take a year
Answer it in the app
🎲 Every Possibility
All the orders you could put things in
To list every arrangement, take each item in turn as the first one, and arrange the rest. Which is a smaller copy of the same problem.
Python
def perms(text):
if len(text) <= 1:
return [text]
out = []
for i in range(len(text)):
for rest in perms(text[:i] + text[i + 1:]):
out.append(text[i] + rest)
return out
print(perms("abc"))It prints
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
The numbers get big fast
Three items give 6 orders, four give 24, ten give over three million. This is why "just try every possibility" only works on small problems.
Python
def count_perms(n):
if n <= 1:
return 1
return n * count_perms(n - 1)
for n in [3, 4, 5, 10]:
print(n, count_perms(n))It prints
3 6 4 24 5 120 10 3628800
Every group you could choose
For subsets, each item is either in or out. So the subsets of a list are the subsets without the first item, plus those same ones with it added.
Python
def subsets(items):
if not items:
return [[]]
rest = subsets(items[1:])
return rest + [[items[0]] + s for s in rest]
for s in subsets([1, 2]):
print(s)It prints
[] [2] [1] [1, 2]
Try it yourself
How many subsets does a list of 3 items have?
- 3
- 6
- 8
- 9
Answer it in the app
↩️ Backtracking
Try, and undo if it fails
Backtracking is recursion that makes a choice, explores it, and then *takes it back* if it leads nowhere. Choose, recurse, un-choose.
Python
chosen = []
def build(depth):
if depth == 2:
print(chosen)
return
for option in ["a", "b"]:
chosen.append(option)
build(depth + 1)
chosen.pop()
build(0)It prints
['a', 'a'] ['a', 'b'] ['b', 'a'] ['b', 'b']
The pop is the whole idea
Without the pop, choices pile up and every later attempt is wrong. Undoing is what lets one list be reused for every path.
Python
chosen = []
def build(depth):
if depth == 2:
print(chosen)
return
for option in ["a", "b"]:
chosen.append(option)
build(depth + 1)
# no pop!
build(0)It prints
['a', 'a'] ['a', 'a', 'b'] ['a', 'a', 'b', 'b', 'a'] ['a', 'a', 'b', 'b', 'a', 'b']
Giving up early saves everything
The real power is refusing a choice that already cannot work, so whole branches are never explored. Here queens are placed one row at a time, and a column that clashes is skipped immediately.
Python
def queens(n):
solutions = []
columns = []
def safe(col):
row = len(columns)
for r, c in enumerate(columns):
if c == col or abs(c - col) == row - r:
return False
return True
def place():
if len(columns) == n:
solutions.append(list(columns))
return
for col in range(n):
if safe(col):
columns.append(col)
place()
columns.pop()
place()
return solutions
for solution in queens(4):
print(solution)It prints
[1, 3, 0, 2] [2, 0, 3, 1]
Try it yourself
What makes backtracking better than listing every possibility?
- It uses recursion
- It abandons a branch the moment it cannot work, so most possibilities are never built
- It is shorter to write
- Nothing, they are the same
Answer it in the app
🏆 Recursion Master
Try it yourself
What does this print?
Python
def f(n):
if n == 0:
return ""
return f(n - 1) + str(n)
print(f(4))Answer it in the app