Recursion

Lesson 20 of 31 · Part 3 · Functions · about 20 minutes

A function can call other functions, and it can also call itself. That is recursion. It sounds like a trick, but it is a natural way to solve a problem that contains a smaller copy of itself. Counting down from 3 is "say 3, then count down from 2":

1def countdown(n):2    if n == 0:3        print("Lights on!")4    else:5        print(n)6        countdown(n - 1)7 8countdown(3)

3
2
1
Lights on!

Every recursive function has two parts:

Each call makes the problem smaller, so sooner or later it reaches the base case and the calls stop.

Factorial

The factorial of 5, written 5!, is 5 × 4 × 3 × 2 × 1 = 120. Look at it another way: 5! is 5 × 4!, and 4! is 4 × 3!, and so on down to 1! = 1. That is already a recursive function:

1def factorial(n):2    if n <= 1:3        return 14    return n * factorial(n - 1)5 6print(factorial(4))7print(factorial(5))

24
120

factorial(4) cannot finish right away: it has to wait for factorial(3), which waits for factorial(2), which waits for factorial(1). That one returns 1, and then the waiting calls finish one by one, in the opposite order: 2 × 1, 3 × 2, 4 × 6.

Tip: Press Step on this example. You can watch the calls stack up until n is 1, then come back down, each one with its own n.

Watching each call

Each call has its own local variables, so n in one call and n in the next are different variables. To see the calls nest, give the function an extra parameter for how deep it is, and indent its messages by that much:

1def factorial(n, depth=0):2    pad = "    " * depth3    print(f"{pad}factorial({n})")4    if n <= 1:5        print(f"{pad}returns 1")6        return 17    result = n * factorial(n - 1, depth + 1)8    print(f"{pad}returns {result}")9    return result10 11factorial(3)

factorial(3)
    factorial(2)
        factorial(1)
        returns 1
    returns 2
returns 6

Python keeps a stack of calls that have started but not finished. Each new call goes on top; each return takes the top one off and hands its value to the call below. The game Infinite Nesting lets you play with exactly this: Wick clones itself level by level, then returns level by level.

1def show(n):2    if n == 0:3        return4    show(n - 1)5    print(n)6 7show(3)

Strings and lists

A string is its first character plus the rest of the string. So to reverse a string: reverse the rest, then put the first character at the end. The empty string is the base case.

1def reverse(text):2    if text == "":3        return ""4    return reverse(text[1:]) + text[0]5 6print(reverse("lamp"))7print(reverse("Wick"))

pmal
kciW

Lists work the same way: the first item, plus the rest of the list. An empty list is the base case.

1def total(items):2    if not items:3        return 04    return items[0] + total(items[1:])5 6def longest(words):7    if len(words) == 1:8        return words[0]9    rest = longest(words[1:])10    return words[0] if len(words[0]) >= len(rest) else rest11 12print(total([3, 8, 2, 6]))13print(longest(["ore", "warehouse", "lamp"]))

19
warehouse

For flat lists like these, a loop or sum() is simpler. Recursion really pays off with the next kind of data.

Nested data

The warehouse keeps ore in crates, and some crates have smaller crates inside, to any depth. A simple loop can't easily handle "any depth", but recursion can: for each item, if it is a number, add it; if it is a crate, count that crate the same way.

1def count_ore(crate):2    total = 03    for item in crate:4        if isinstance(item, list):5            total += count_ore(item)6        else:7            total += item8    return total9 10warehouse = [4, [2, 3], [1, [5, 6]], 7]11print(count_ore(warehouse))

28

isinstance(item, list) asks "is item a list?" and gives True or False (lesson 27 says more). Here the base case is not an if at the top: it is a crate with no crates inside, where the loop finishes without calling count_ore again.

Forgetting the base case

Without a base case, nothing stops the calls. This total should add up 3 + 2 + 1, but it never stops at 0:

1def total(n):2    return n + total(n - 1)3 4print(total(3))

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

Every call is waiting for the next one, so the stack of calls keeps growing. Python stops after too many levels and raises a RecursionError. In standard Python the limit is 1000 levels by default. If you see this error, check two things: is there a base case, and does every call really get closer to it?

1def countdown(n):2    if n == 0:3        print("Done")4        return5    countdown(n - 2)6 7countdown(5)

Fibonacci's repeated work

In the Fibonacci numbers 0, 1, 1, 2, 3, 5, 8, 13…, each number is the sum of the two before it. That translates straight into a function with two recursive calls. Let's count how many calls it makes, with a global counter:

1calls = 02 3def fib(n):4    global calls5    calls += 16    if n < 2:7        return n8    return fib(n - 1) + fib(n - 2)9 10for n in [5, 10, 15]:11    calls = 012    result = fib(n)13    print(f"fib({n}) = {result} after {calls} calls")

fib(5) = 5 after 15 calls
fib(10) = 55 after 177 calls
fib(15) = 610 after 1973 calls

The count grows much faster than n. The reason is repeated work: fib(5) calls fib(4) and fib(3), but fib(4) also calls fib(3), and each of those works out fib(2) again, and so on. A loop that remembers the last two numbers does each step once:

1def fib(n):2    a, b = 0, 13    for step in range(n):4        a, b = b, a + b5    return a6 7print(fib(15))8print(fib(50))

610
12586269025

Recursion or a loop?

Anything recursion can do, a loop can do too, and the other way around. Pick the one that matches the shape of the problem:

The last row matters because every level of recursion stays on the stack until it returns:

1def sum_to(n):2    if n == 0:3        return 04    return n + sum_to(n - 1)5 6def sum_to_loop(n):7    total = 08    for i in range(1, n + 1):9        total += i10    return total11 12print(sum_to(100))13print(sum_to_loop(5000))14print(sum_to(5000))

5050
12502500
Traceback (most recent call last):
  File "main.py", line 14, in <module>
    print(sum_to(5000))
  File "main.py", line 4, in sum_to
    return n + sum_to(n - 1)
  File "main.py", line 4, in sum_to
    return n + sum_to(n - 1)
  File "main.py", line 4, in sum_to
    return n + sum_to(n - 1)
  [Previous line repeated 297 more times]
RecursionError: maximum recursion depth exceeded

The last line goes past Python's limit on how deep recursion may go and raises a RecursionError. The loop has no such limit.

Practice

Write the code, then press Check. A hint costs nothing; the answer is there when you need it. Solve each one with recursion, and start with the base case.

1024
81

1def power(base, exp):2    return 03 4print(power(2, 10))5print(power(3, 4))

2
0

1def count_char(text, ch):2    return 03 4print(count_char("lamplighter", "l"))5print(count_char("ore", "x"))

[1, 2, 3, 4, 5]

1def flatten(crate):2    result = []3    for item in crate:4        result.append(item)5    return result6 7print(flatten([1, [2, 3], [[4], 5]]))

What you learned

• A recursive function calls itself on a smaller problem, until it reaches a base case it can answer directly.
• Each call has its own local variables; unfinished calls wait on a stack and finish in reverse order.
• Strings and lists split into "first item + the rest"; nested data splits into "this level + the levels inside".
• No base case, or one that is never reached, ends in a RecursionError.
• Recursion can repeat work (like fib) and can only go so deep; for simple step-by-step jobs, a loop is often better.