Learn/Python/11. Recursion
Lesson 11 of 15
Sign in

Python, lesson 11

Recursion

A recursive function is one that calls itself. That sounds like a recipe for an endless loop, but it's a natural way to solve problems that contain smaller copies of themselves: a folder holds folders, a family tree holds smaller family trees, and the sum of a list is the first number plus the sum of the rest.

The two parts every recursive function needs

  1. A base case: an input small enough to answer directly, without recursing.
  2. A recursive case: break the problem into a smaller piece, call the function on that piece, and use its answer.

Each call must move closer to the base case. If it doesn't, the calls never stop.

Returning values up the chain

Most recursive functions return a result that the caller builds on:

Trace factorial(3): it needs factorial(2), which needs factorial(1), which returns 1. Then the answers flow back up: , then .

2 exercises to try what you just read.

Exercise 1

Digital root

Press Ctrl Enter or Check to test your code.

Exercise 2

Staircase paths

Press Ctrl Enter or Check to test your code.

2 * 1 = 2
3 * 2 = 6

Every call that hasn't finished yet waits on the call stack, with its own copy of its local variables. That's why n doesn't get overwritten as the calls go deeper.

How deep can you go?

Python limits the depth of the call stack to protect itself; by default the limit is about 1000 calls. Going deeper raises RecursionError. You can inspect the limit with sys.getrecursionlimit() and raise it with sys.setrecursionlimit(), but if you need tens of thousands of levels, a loop is usually the better tool. Python does not optimise tail calls, so recursion is always a little more expensive than a loop.

Recursion on structures

Recursion shines when the data itself is nested. This function adds up numbers in lists that may contain other lists, to any depth:

Writing that with plain loops would be awkward, because you don't know how deep the nesting goes.

Remembering answers with a cache

Some recursive functions solve the same small problem many times over. The classic example is Fibonacci: fib(30) calls fib(28) twice, fib(27) three times, and so on. The number of calls explodes.

functools.cache fixes this by remembering every result. The second time the function is called with the same arguments, the stored answer comes straight back:

This technique is called memoisation. It works whenever the function always returns the same output for the same input and its arguments are hashable (numbers, strings, tuples).

Thinking recursively

Don't try to follow every call in your head. Instead, trust that the recursive call correctly solves the smaller problem, and ask only: "given that answer, how do I finish this one?" Then check that the base case is right and that every call shrinks the input.

Further reading

  • The Python Tutorial: Defining functions
  • functools.cache
  • sys.setrecursionlimit()

The digital root of a number is what you get by adding up its digits, then adding up the digits of that result, and so on until one digit is left. For 9875: 9+8+7+5 = 29, then 2+9 = 11, then 1+1 = 2.

Write two recursive functions: digit_sum(n) returns the sum of the digits of n (use n % 10 and n // 10), and digital_root(n) uses it until a single digit remains. Read one non-negative whole number and print its digital root.

Sample input:

Sample output:

You can climb a staircase one or two steps at a time. To reach step n your last move came either from step n - 1 or from step n - 2, so the number of ways to reach n is ways(n - 1) + ways(n - 2). There is exactly one way to reach step 0 (stay put) and one way to reach step 1.

Read n (0 to 90) and print the number of different ways to climb to the top. Large n is far too slow without a cache, so decorate your function with @cache.

Sample input:

Sample output:

def countdown(n):
    if n == 0:              # base case
        print("Go!")
        return
    print(n)
    countdown(n - 1)        # recursive case: a smaller problem
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)
def deep_sum(items):
    total = 0
    for item in items:
        if isinstance(item, list):
            total += deep_sum(item)    # a smaller copy of the same problem
        else:
            total += item
    return total

print(deep_sum([1, [2, 3], [[4], 5]]))   # 15
from functools import cache

@cache
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(90))   # instant
9875
2
4
5