Recursion

A recursive function is a function that calls itself. It solves a problem by breaking it into a smaller version of the same problem, and keeps going until the problem is small enough to answer directly.

A first example: countdown

def countdown(n):
    if n == 0:
        print("Liftoff!")
        return
    print(n)
    countdown(n - 1)

countdown(5)

Every recursive function needs two parts:

1. A base case: a simple situation answered directly, without recursion. Here it's n == 0.
2. A recursive case: the function calls itself with a smaller problem, here n - 1, moving towards the base case.

Here's what happens: countdown(5) prints 5 and calls countdown(4), which prints 4 and calls countdown(3), and so on. countdown(0) hits the base case: it prints Liftoff! and returns without calling itself again, so the chain stops. Each call is a separate run of the function, with its own n.

Factorial

The factorial of n, written n!, is n × (n − 1) × … × 1. So 5! = 5 × 4 × 3 × 2 × 1 = 120.

Notice that 5! = 5 × 4!. The factorial is defined in terms of a smaller factorial, which makes it a natural fit for recursion:

def factorial(n):
    # base case
    if n <= 1:
        return 1
    # recursive case
    return n * factorial(n - 1)

print(factorial(5))
print(factorial(10))

Here's what happens for factorial(4):

factorial(4) = 4 * factorial(3)
             = 4 * (3 * factorial(2))
             = 4 * (3 * (2 * factorial(1)))
             = 4 * (3 * (2 * 1))
             = 24

Each call waits for the one below it to return, then finishes its own multiplication. The calls go down until factorial(1) returns 1 without recursing. Then the answers come back up: 2 * 1 = 2, then 3 * 2 = 6, then 4 * 6 = 24.

Seeing the calls

Printing with indentation makes the calls visible:

def factorial(n, depth=0):
    indent = "  " * depth
    print(f"{indent}factorial({n})")
    if n <= 1:
        result = 1
    else:
        result = n * factorial(n - 1, depth + 1)
    print(f"{indent}-> {result}")
    return result

factorial(4)

Recursion on strings and lists

Recursion works well whenever data has a "first item plus the rest" shape:

def reverse(text):
    if text == "":
        return ""
    return reverse(text[1:]) + text[0]

def total(numbers):
    if not numbers:
        return 0
    return numbers[0] + total(numbers[1:])

print(reverse("python"))
print(total([4, 8, 15, 16, 23, 42]))

Both follow the same plan: handle the first item, and let a recursive call handle the rest (text[1:] or numbers[1:], which is one item shorter each time). For reverse("abc"):

reverse("abc") = reverse("bc") + "a"
               = (reverse("c") + "b") + "a"
               = ((reverse("") + "c") + "b") + "a"
               = "" + "c" + "b" + "a"
               = "cba"

The base case is the empty string or empty list, where there's nothing left to do. if not numbers: uses truthiness: an empty list is falsy, so this means "if the list is empty".

Nested data

Recursion really shines with data that contains smaller copies of itself, like lists inside lists:

def flatten(items):
    flat = []
    for item in items:
        if isinstance(item, list):
            # recurse into the inner list
            flat.extend(flatten(item))
        else:
            flat.append(item)
    return flat

print(flatten([1, [2, 3], [4, [5, [6, 7]]], 8]))

isinstance(item, list) asks "is item a list?" and gives True or False. Plain numbers are added straight to flat. For an inner list, flatten calls itself to flatten that list first, then adds all of its items with extend(). However deep the nesting goes, each level is handled by one more call.

Doing this with plain loops is awkward, because you don't know in advance how deep the nesting goes.

Forgetting the base case

Without a base case, or with one that's never reached, the function calls itself forever: 3, 2, 1, 0, -1, -2… Python stops it with a RecursionError:

def countdown(n):
    # no base case: never stops!
    countdown(n - 1)

countdown(3)

Python limits how deep recursion can go, to protect your program. Every call that hasn't finished yet takes up memory, so Python stops after about 1,000 calls waiting at once. A "maximum recursion depth exceeded" message almost always means a missing or unreachable base case. You can check the limit:

import sys
print(sys.getrecursionlimit())

Fibonacci and the cost of repeated work

In the Fibonacci sequence, each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13… A direct recursive version is short:

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

print([fib(i) for i in range(10)])

But it's slow for bigger numbers, because it recalculates the same values again and again. fib(5) calls fib(4) and fib(3), but fib(4) calls fib(3) again, and each of those calls fib(2)… The number of calls roughly doubles with each step up, so fib(30) makes over a million calls. Remembering results that are already known, called memoization, fixes that:

from functools import lru_cache

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

print(fib(30))
print(fib(100))

With the cache, each fib(n) is calculated only once; after that, the stored answer is returned straight away. That's why even fib(100) is instant. The @lru_cache line is a decorator. You'll learn how those work in the Decorators lesson.

Recursion or a loop?

Anything recursive can also be written with a loop, and for simple counting a loop is usually clearer and faster:

def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_loop(5))

Reach for recursion when the problem is naturally recursive: nested data, trees, folders inside folders, or divide-and-conquer algorithms.

Exercises

Exercise 1: Sum to n

Write a recursive function sum_to(n) that returns 1 + 2 + ... + n. sum_to(10) should be 55.

def sum_to(n):
    pass

print(sum_to(10))

Exercise 2: Power

Write a recursive power(base, exp) without using **. power(2, 10) should be 1024.

def power(base, exp):
    pass

print(power(2, 10))
print(power(3, 0))

Exercise 3: Count down and up

Write bounce(n) that prints the numbers from n down to 1 and then back up to n. Hint: put a print both before and after the recursive call. For bounce(3) it should print 3 2 1 1 2 3 (one per line).

def bounce(n):
    pass

bounce(3)

Exercise 4: Palindrome

Write a recursive is_palindrome(text): a string is a palindrome if its first and last characters match and the middle part is a palindrome. Empty strings and single characters are palindromes.

def is_palindrome(text):
    pass

print(is_palindrome("racecar"))
print(is_palindrome("python"))

Summary

• A recursive function calls itself on a smaller version of the problem.
• Every recursive function needs a base case that stops the recursion.
• Each call waits for the call below it, and the results combine on the way back up.
• Missing or unreachable base cases cause a RecursionError.
• Naive recursion can repeat work. functools.lru_cache remembers results.
• Use recursion for naturally recursive problems such as nested data, and loops for simple repetition.