Lesson 5 of 5 · Functions · 2 min read · Updated

Recursion

A function that calls itself — how it stops, and when it is the natural answer.

A recursive function solves a problem by calling itself on a smaller piece of the same problem. It needs a base case — a point where it answers directly instead of calling itself again.

python
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))
Output
120

Example

factorial(5) is 5 × factorial(4), which is 4 × factorial(3), and so on down to factorial(1), the base case, which returns 1. Then the answers multiply back up: 1 × 2 × 3 × 4 × 5 = 120.

Where recursion shines

python
def total(items):
    result = 0
    for item in items:
        if isinstance(item, list):
            result += total(item)
        else:
            result += item
    return result

print(total([1, [2, 3], [4, [5, 6]]]))
Output
21

Factorial is easy to write with a loop too. Recursion earns its place with data that contains smaller versions of itself — lists inside lists, folders inside folders — where you do not know in advance how deep it goes.

Warning

Forget the base case, or never reach it, and the function calls itself until Python stops it with RecursionError: maximum recursion depth exceeded — about 1000 calls deep by default.

What must every recursive function have?

Try this now

  1. Write a recursive countdown(n) that prints n down to 1 and then "Go!".
  2. Write a recursive function that reverses a string: the last letter plus the reverse of the rest.
  3. Write fib(n) for Fibonacci numbers recursively, then notice how slow fib(35) is — and think about why.

Create a free account to save your progress, or sign in.