Recursion

The queue problem has a special shape: inside it is a smaller copy of the same problem. “How many are ahead of me?” is one more than “how many are ahead of the person in front of me?”, which is the same question about a queue one person shorter.

Many problems have this shape once you look for it.

• A folder on a computer. How much space does it take? Its files, plus the space each folder inside it takes: the same question about a smaller folder.
• A family tree. Who are your grandfather’s descendants? His children, and each child’s descendants: the same question about someone lower in the tree.
• A word written backwards. “Pokhara” backwards is “ahkoP” backwards with the first letter, P, put on the end: the same job on a shorter word.

Solving a problem by solving smaller copies of the same problem is called recursion. A recursive solution always has two parts:

• The base case: a copy so small that you can answer it straight away, without asking anything. The person at the counter: “none”. An empty folder: no space. A word with no letters: backwards it is still nothing.
• The recursive case: the rule that answers a bigger copy using the answer to a smaller one. “One more than the answer of the person in front.”

The base case is what makes the whole thing stop. Without it, the questions would go on for ever.

Say it in words first

Before writing any code, write the two cases in a sentence each. If you can’t, you haven’t found the smaller copy yet.

In Grade 8 you wrote functions with parameters and return values, and in Grade 10 you saw that every call of a function gets its own box of names. A function may call any function, including itself. A function that calls itself is a recursive function.

How many ways can four friends stand in a line for a photo? Any of the 4 can stand first; then any of the other 3 second; then 2; then 1: 4 × 3 × 2 × 1 = 24 ways. This product is written 4! and called 4 factorial. In general n! = n × (n − 1) × … × 2 × 1, and mathematicians agree that 0! = 1 (there is exactly one way to line up nobody: do nothing). Look at it again: 4! = 4 × 3!, and 3! = 3 × 2!. Factorial has a smaller copy inside.

def factorial(n):    if n == 0:        return 1    return n * factorial(n - 1) print(factorial(4))print(factorial(10))

243628800

Lines 2 and 3 are the base case, 0! = 1. Line 4 is the recursive case, n! = n × (n − 1)!: to find factorial(4), the function calls factorial(3), and so on down.

Watching the calls

What really happens when the program calls factorial(4)? Step through it and watch.

Three things to notice:

• Each call has its own n. As in Grade 10, every call gets a box of its own names. There are five variables called n at once, holding 4, 3, 2, 1 and 0, and they never mix.
• A call waits for the one it made. factorial(4) can’t finish its multiplication until factorial(3) gives back its answer, so it waits, part-done. On the way down, nothing is multiplied at all: the calls just pile up, each waiting.
• The answers come back in the opposite order. The last call made, factorial(0), is the first to finish. Then factorial(1) finishes, then factorial(2), and the first call made is the last to finish. A pile where the last one on is the first one off is a stack, and this pile of waiting calls is the call stack you met in Grade 10. Unit 4, From Code to Circuits, shows how the computer keeps it in its memory.

Three questions for every recursive function

Writing a recursive function feels strange at first, because you use the function before you have finished writing it. Ask three questions, and it becomes routine:

1. What is the base case, and what does it give back? (The smallest problem: 0!, an empty list.)
2. How does each call make the problem smaller, so that it is sure to reach the base case? (n − 1, the list without its first item.)
3. Pretend the smaller call already works. If factorial(n − 1) gives the right answer, how do I make factorial(n) from it? (Multiply by n.)

The third question is the trick. Don’t follow the calls all the way down in your head; you just did that once with the widget, and it always works the same way. Trust that the smaller copy is solved, and only write the one step that builds on it. Programmers call this the recursive leap of faith: it isn’t blind faith, because questions 1 and 2 make sure the calls really do end.

Lists and words

A list has a smaller copy inside too: the list without its first item. In Grade 9 you took parts of a list with slices; numbers[1:] is everything after the first item, and text[1:] everything after the first letter.

def total(numbers):    """The total of a list of numbers."""    if numbers == []:        return 0    return numbers[0] + total(numbers[1:]) def reverse(text):    """The text written backwards."""    if text == "":        return ""    return reverse(text[1:]) + text[0] print(total([45, 72, 63, 38]))print(reverse("Pokhara"))

218arahkoP

Ask the three questions of reverse. The base case: an empty word backwards is empty. Smaller: each call has one letter fewer. Pretend it works: if reverse("okhara") gives "arahko", then putting the first letter, "P", on the end gives "arahkoP".

Things inside things: a folder’s size

Recursion is most at home with things inside things: folders inside folders, branches on branches, a family tree. Here is a folder of school work, written as a dictionary (Grade 9): a file’s name gives its size in kilobytes, and a folder’s name gives another dictionary, its contents.

school = {    "notes.txt": 12,    "homework": {"math.pdf": 350, "science.pdf": 410},    "photos": {        "tihar.jpg": 2400,        "trip": {"nagarkot.jpg": 3100, "bhaktapur.jpg": 2800},    },} def size(folder):    """The total size of everything in a folder, folders inside it too."""    total = 0    for name in folder:        item = folder[name]        if type(item) == dict:            total = total + size(item)        else:            total = total + item    return total print(size(school))print(size(school["photos"]))

90728300

size adds up the files with a loop, and for every folder inside, calls itself. Where is the base case? A folder with no folders inside: the loop adds its files and never calls size again. However deep the folders go, five levels or fifty, the same ten lines find the total. With plain loops, one inside another, you would need a loop for every level, and you would have to know in advance how deep the folders go. (A loop can do it, with a list of its own of the folders still to look at: you will see how later in this unit. The recursion is simply the clearer way to say it.)

A recursive function must reach its base case. If it doesn’t, each call makes another call, which makes another, and none of them ever finishes. Here someone counts the strides needed to climb a stairway two steps at a time, with a base case at 0:

def stairs(n):    if n == 0:        return 0    return 1 + stairs(n - 2) print(stairs(8))print(stairs(7))

Traceback (most recent call last):  File "main.py", line 7, in <module>    print(stairs(7))          ~~~~~~^^^  File "main.py", line 4, in stairs    return 1 + stairs(n - 2)               ~~~~~~^^^^^^^  File "main.py", line 4, in stairs    return 1 + stairs(n - 2)               ~~~~~~^^^^^^^  File "main.py", line 4, in stairs    return 1 + stairs(n - 2)               ~~~~~~^^^^^^^  [Previous line repeated 994 more times]RecursionError: maximum recursion depth exceeded

stairs(8) prints 4 and is fine: 8, 6, 4, 2, 0. But from 7, n goes 7, 5, 3, 1, −1, −3, … and jumps straight over 0. Every call waits for the next, the open calls pile up, and Python stops the program when about a thousand of them are open, with a RecursionError. The traceback would be a thousand lines long, so Python prints a few and says the last line was repeated.

Python sets this limit, the recursion limit, to protect the computer: every open call takes up some memory, and without a limit a runaway recursion would fill it and crash the program, or worse. Unit 4, From Code to Circuits, shows the memory the open calls fill, the call stack.

There are three classic ways to get recursion wrong:

1. No base case, or one the calls can jump over, as in stairs: a RecursionError.
2. A base case that gives back the wrong answer: the program may stop with another error, or, worse, finish with a wrong answer and no warning.
3. Forgetting return in the recursive case: the call works out its answer and throws it away. A function that ends without return gives back None, and the call waiting for it gets None instead of a number.

Here is a puzzle that looks hard and becomes easy the moment you think recursively. There are three pegs, A, B and C, and on A a tower of disks, each smaller than the one below. Move the whole tower to C. The rules:

• Move one disk at a time: the top disk of any peg, onto another peg.
• Never put a disk on top of a smaller one.

Thinking recursively

Look at the biggest disk. To move it from A to C, C must be empty (nothing can sit under the biggest disk) and nothing can be on top of it. So at that moment, all the other disks must be on B. Now the whole solution falls out:

1. Move the top n − 1 disks from A to B, using C as the spare peg.
2. Move the biggest disk from A to C.
3. Move the n − 1 disks from B to C, using A as the spare.

Steps 1 and 3 are the same puzzle, a tower of n − 1 disks, smaller by one disk. That is the smaller copy inside. And the base case: a tower of 0 disks needs no moves at all.

In Python it is barely longer than the description:

def hanoi(n, start, goal, spare):    """Print the moves that take n disks from start to goal."""    if n == 0:        return    hanoi(n - 1, start, spare, goal)    print("Move disk", n, "from", start, "to", goal)    hanoi(n - 1, spare, goal, start) hanoi(3, "A", "C", "B")

Move disk 1 from A to CMove disk 2 from A to BMove disk 1 from C to BMove disk 3 from A to CMove disk 1 from B to AMove disk 2 from B to CMove disk 1 from A to C

Line 5 moves the smaller tower out of the way: from start to spare, so the spare peg of this call is the goal of that one. Line 6 moves the biggest disk. Line 7 brings the smaller tower from spare to goal. Change the 3 to 4 or 5 and press Run: the same seven lines solve any tower.

Go back to the widget and press Watch the solution. The list under it shows the jobs waiting, each job given out by the one above it: “move 3 disks from A to C” waits while “move 2 disks from A to B” is done, which waits for “move 1 disk from A to C”. Those are the open calls of hanoi.

How many moves?

Let M(n) be the number of moves for n disks. The three steps take M(n − 1) moves, then 1 move, then M(n − 1) moves again, so

$$M(n) = 2 \times M(n-1) + 1, \qquad M(0) = 0$$

Each number is one less than a power of 2: M(n) = 2ⁿ − 1. You can check that the rule keeps it so: if M(n − 1) = 2ⁿ⁻¹ − 1, then M(n) = 2 × (2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 2 + 1 = 2ⁿ − 1. It is also the fewest possible. The biggest disk must move at least once. Before its first move, the other n − 1 disks must all be stacked on the third peg, out of its way: building that tower takes at least M(n − 1) moves. After its last move, onto C, those n − 1 disks must all be moved from one peg onto it: at least M(n − 1) moves again. So any solution takes at least M(n − 1) + 1 + M(n − 1) moves, exactly what the recursive method uses, and no player, however clever, beats 2ⁿ − 1.

Look at a fern’s leaf: it is made of small leaflets, and each leaflet looks like a small fern leaf. A tree’s branch looks like a small tree. A picture made of smaller copies of itself is called a fractal, and recursion draws one easily: to draw the picture, draw a smaller copy of the picture, in a few places.

Take a tree. To draw a tree: draw the trunk, then on top of it draw two smaller trees, one leaning left and one leaning right. Each smaller tree is a trunk with two still smaller trees on top. The base case is a tree of depth 0: just a trunk.

Here is the tree with Python’s turtle, which you used in Grade 8. The turtle draws the trunk, turns 25° left and draws a smaller tree, turns 50° right and draws another, then turns back and walks back down the trunk, so that it ends where it started, facing the same way. That last part matters: each call must leave the turtle exactly where it found it, or the next branch would start in the wrong place.

import turtlet = turtle.Turtle()t.penup()t.goto(0, -150)t.pendown()t.left(90) def tree(length, depth):    t.forward(length)    if depth > 0:        t.left(25)        tree(length * 0.7, depth - 1)        t.right(50)        tree(length * 0.7, depth - 1)        t.left(25)    t.backward(length) tree(100, 6)

There is no return for the base case here: when depth is 0, the if is skipped, and the trunk is drawn and walked back, which is all a depth-0 tree is.

Every drawing app has a paint bucket: tap inside a shape, and the whole area turns your color, right up to its outline, however twisted its shape. In Grade 6 you saw that a picture is a grid of pixels. How does the app know which pixels are inside the area you tapped?

It doesn’t, until it looks, and it looks recursively. To fill from a pixel: if the pixel is off the picture, or isn’t the color being replaced, stop: that is the base case (an outline, the edge, or a pixel already filled). Otherwise, color it, and fill from each of its four neighbors, up, down, left and right. This is flood fill.

Here is flood fill in Python, on a picture made of characters, # for the outline and . for empty. It colors with o and gives back how many squares it colored.

picture = [    "##########",    "#....#...#",    "#....#...#",    "#.####...#",    "#....#...#",    "##########",]grid = [list(row) for row in picture] def fill(grid, r, c, old, new):    """Color the area of old squares that includes (r, c); give back how many."""    if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):        return 0    if grid[r][c] != old:        return 0    grid[r][c] = new    count = 1    count = count + fill(grid, r - 1, c, old, new)    count = count + fill(grid, r + 1, c, old, new)    count = count + fill(grid, r, c - 1, old, new)    count = count + fill(grid, r, c + 1, old, new)    return count print(fill(grid, 1, 1, ".", "o"), "squares colored")for row in grid:    print("".join(row))

13 squares colored###########oooo#...##oooo#...##o####...##oooo#...###########

Line 13 is the edge of the picture and line 15 the outline or a square already colored: both are base cases, and both give back 0. Line 17 colors the square before it fills the neighbors. That order matters: when a neighbor fills back towards this square, it finds it already o, not ., and stops. Color it after, and the neighbors would call each other back and forth for ever.

When the area is huge

A phone photo has millions of pixels, and the area of sky in it might have a million. Flood fill makes one call per pixel, and while it snakes across the sky the calls stay open behind it: on a long path, hundreds of thousands of them, far past Python’s limit of about a thousand. Even one row of a phone photo, about 4,000 pixels across, is too much:

def fill(grid, r, c, old, new):    if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):        return 0    if grid[r][c] != old:        return 0    grid[r][c] = new    count = 1    count = count + fill(grid, r - 1, c, old, new)    count = count + fill(grid, r + 1, c, old, new)    count = count + fill(grid, r, c - 1, old, new)    count = count + fill(grid, r, c + 1, old, new)    return count row = [["."] * 4000]print(fill(row, 0, 0, ".", "o"))

Traceback (most recent call last):  File "main.py", line 15, in <module>    print(fill(row, 0, 0, ".", "o"))          ~~~~^^^^^^^^^^^^^^^^^^^^^  File "main.py", line 11, in fill    count = count + fill(grid, r, c + 1, old, new)                    ~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^  File "main.py", line 11, in fill    count = count + fill(grid, r, c + 1, old, new)                    ~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^  File "main.py", line 11, in fill    count = count + fill(grid, r, c + 1, old, new)                    ~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^  [Previous line repeated 993 more times]  File "main.py", line 8, in fill    count = count + fill(grid, r - 1, c, old, new)                    ~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^RecursionError: maximum recursion depth exceeded

Each square calls fill on the square to its right, which calls the next, and none can finish until the end of the row is reached. The answer is to do the same work with a loop, keeping the squares still to do in a list of your own, which can grow as long as memory allows. Instead of calling fill on a neighbor, put it on the list; instead of a call finishing, take the next square off the list:

def fill(grid, r, c, old, new):    """Flood fill with a loop and a list of squares still to do."""    to_do = [(r, c)]    count = 0    while to_do != []:        r, c = to_do.pop()        if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):            continue        if grid[r][c] != old:            continue        grid[r][c] = new        count = count + 1        to_do.append((r, c + 1))        to_do.append((r, c - 1))        to_do.append((r + 1, c))        to_do.append((r - 1, c))    return count row = [["."] * 4000]print(fill(row, 0, 0, ".", "o"))sky = [["."] * 300 for i in range(200)]print(fill(sky, 0, 0, ".", "o"))

400060000

The list to_do does the job of the open calls: pop() takes the newest square, just as the newest call is the first to finish, so this loop colors the squares in the same order as the recursive fill (the neighbors go on in reverse, so that “up” comes off first). In Grade 10 you met this exact choice: a list taken from the end it is added to is a stack, and searching with one is depth-first search. Unit 3 of this book builds stacks of its own. Any recursion can be turned into a loop with a stack like this; recursion is often the clearer way to write it, and the loop the safer way to run it on big data.

In Grade 9 you sorted with merge sort: start with piles of one item, merge them in pairs, then merge those, round after round, until one pile is left. Now look at it from the top instead. To sort a list:

• Base case: a list of 0 or 1 items is already sorted.
• Recursive case: split the list in half, sort each half (a smaller copy of the same problem), and merge the two sorted halves.

That is the whole algorithm. The merging is the same as in Grade 9, without the count of comparisons.

def merge(a, b):    c = []    i = 0    j = 0    while i < len(a) and j < len(b):        if a[i] <= b[j]:            c.append(a[i])            i = i + 1        else:            c.append(b[j])            j = j + 1    return c + a[i:] + b[j:] def merge_sort(items):    if len(items) <= 1:        return items    mid = len(items) // 2    left = merge_sort(items[:mid])    right = merge_sort(items[mid:])    return merge(left, right) print(merge_sort([62, 38, 85, 29, 91, 54, 70, 47]))print(merge_sort(["Pokhara", "Biratnagar", "Dhangadhi", "Hetauda", "Janakpur"]))

[29, 38, 47, 54, 62, 70, 85, 91]['Biratnagar', 'Dhangadhi', 'Hetauda', 'Janakpur', 'Pokhara']

i and j point to the next item of each half. When one half is used up, a[i:] + b[j:] puts what is left of the other on the end. (It might look neater to take the first item off a list with a.pop(0), but that moves every item behind it one place forward, so the merge would no longer take about one step per item, and merge sort would lose its speed.)

Why is it fast? The tree of calls has about log₂ n levels, because each level halves the lists, and the merges on each level handle every item once, about n steps a level. So merge sort takes about n × log₂ n steps, the O(n log n) of Grade 9, now seen from the shape of the recursion. And its depth is only about log₂ n: a million items need only about 21 open calls, so the recursion limit is never a problem for merge sort.

Recursion isn’t always the best tool. Here is factorial written with a loop:

def factorial(n):    result = 1    for i in range(2, n + 1):        result = result * i    return result print(factorial(4), factorial(20))

24 2432902008176640000

It is just as clear, has no calls waiting, and works for factorial(5000), where the recursive version would hit the recursion limit. Factorial is a straight line: each step leads to exactly one smaller step. For a straight line, a loop is usually better.

Counting the ways up a stairway

Climbing the steps of a temple, you take one step or two at a time. In how many different ways can you climb 5 steps? Your first move is either one step, leaving 4 steps, or two steps, leaving 3. So the ways for 5 steps are the ways for 4 plus the ways for 3. With 0 or 1 steps left there is only 1 way.

def ways(n):    if n <= 1:        return 1    return ways(n - 1) + ways(n - 2) print(ways(5), ways(10), ways(20))

8 89 10946

That is correct and very short. But watch what it does.

Each call makes two calls, so the tree of calls branches like the fractal tree, and the same questions are asked again and again in different branches. The calls needed grow almost as fast as doubling with each step:

ways(40) makes over 330 million calls, which keeps a fast computer busy for about ten seconds, and a phone much longer; ways(60) would make about five million million calls and take days. A loop that keeps just the last two answers, and works upwards from the bottom, goes round the loop only 39 times:

def ways(n):    a = 1            # the ways for 0 steps    b = 1            # the ways for 1 step    for i in range(n - 1):        a, b = b, a + b    return b print(ways(5), ways(40))

8 165580141

The recursive version is a perfect description of the problem and a terrible way to compute it. Another fix keeps the recursion but remembers every answer the first time it is worked out, so it is never worked out twice; that idea, dynamic programming, is a big part of Grade 12.

Choosing

Use recursion when the problem branches, or is made of things inside things:

• trees of any kind: folders, family trees, the branches of a fractal;
• “split it and solve the pieces”: merge sort, the Tower of Hanoi, binary search;
• exploring every path, as flood fill does, when the paths aren’t too long.

Use a loop when:

• the problem is a straight line, one step leading to one smaller step (factorial, counting down, adding up a list): a loop is as clear, and has no limit on its length;
• the recursion would go thousands of calls deep (a big flood fill): a loop with a list of your own;
• the recursion asks the same questions again and again (ways): a loop that works upwards, or remembered answers.

Choose one, and write it in Python. You can write and run each program on this page, even on a phone (edit a program and press Run); the folder project needs a computer.

• A fractal of your own. Design a fractal with the turtle: a tree with three branches or with branches that get thinner, a snowflake, a fern, or a pattern from a Newar window or a mandala made of smaller copies of itself. Write the base case and recursive case in words first. Then make a table of the number of lines at depths 0 to 5, worked out by a formula, and check it with a counter in your program.
• A paint program on a grid. Start from the flood fill. Let the user type a row, a column and a color letter, fill that area, and print the picture again; repeat until they type q. Add a second picture of your own, and a count of the separate areas in it (fill each empty square you find, counting the fills).
• A folder report. On a computer, write a recursive function that lists every file in a folder and the folders inside it, with sizes, and prints each folder’s total, indented by its depth. Python’s os module gives what you need:

import os def folder_size(path, depth):    total = 0    for entry in os.scandir(path):        if entry.is_dir():            total = total + folder_size(entry.path, depth + 1)        else:            total = total + entry.stat().st_size    print("  " * depth + os.path.basename(path), total, "bytes")    return total

For any project:

1. Say it in words. Write the base case and the recursive case, and check that every call gets closer to a base case.
2. Start tiny. Test the base case alone, then one step up (depth 1, a list of one item, a folder with no folders).
3. Trace a small call by hand, as the CallTree widget does: the calls open, and the value each gives back. Compare with what your program prints.
4. Try it on something big. Does it hit the recursion limit, or repeat work? If so, decide whether a loop would be better, and explain why.