Python Recursion Explained: Base Case, Recursive Case and Examples

A recursive function is a function that calls itself. It solves a problem by breaking it into a smaller version of the same problem, until the problem is small enough to answer directly. Recursion is a natural fit for things that contain smaller copies of themselves: nested folders, family trees, menus within menus.

The two parts of every recursive function#

1. A base case: a simple situation answered directly, without recursing. This is what stops the recursion.
2. A recursive case: the function calls itself with a smaller input, moving toward the base case.

A first example: countdown#

def countdown(n):
    if n == 0:              # base case
        print("Lift off!")
        return
    print(n)
    countdown(n - 1)        # recursive case: smaller problem

countdown(3)

3
2
1
Lift off!

Each call handles one number and hands the rest of the work to a new call with n - 1, until n reaches 0.

Factorial#

The factorial of n (written n!) is n × (n−1) × … × 1. Notice that 5! = 5 × 4!: the problem contains a smaller version of itself.

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

print(factorial(5), factorial(1), factorial(10))

120 1 3628800

How factorial(4) unfolds:

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.

Recursion on lists#

Sum a list as "the first item plus the sum of the rest":

def total(numbers):
    if not numbers:                          # base case: empty list
        return 0
    return numbers[0] + total(numbers[1:])   # recursive case

print(total([4, 8, 15, 16]))

43

Recursion really shines on nested data, where a loop alone cannot know how deep to go:

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

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

[1, 2, 3, 4, 5, 6]

Fibonacci and repeated work#

Each Fibonacci number is the sum of the two before it:

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

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

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

This is elegant but very slow for large n, because the same values are recalculated over and over: fib(30) makes over a million calls. Memoization caches results so each value is computed once:

from functools import lru_cache

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

print(fib(80))

23416728348467685

@lru_cache is a decorator that remembers previous results.

The recursion limit#

Without a base case (or with a base case that is never reached), a function calls itself until Python stops it:

def forever(n):
    return forever(n + 1)

forever(0)

RecursionError: maximum recursion depth exceeded

import sys
print(sys.getrecursionlimit())

1000

Python limits recursion to about 1,000 nested calls by default, to protect against crashes. For problems that need deeper recursion (such as summing a list of 100,000 items), use a loop instead.

Recursion or a loop?#

Common mistakes#

Practice#

def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)

print(digit_sum(4815), digit_sum(7))

18 7

Key takeaway#