Python Recursion

Recursion is when a function calls itself. A function in Python can do that, and it can be pretty useful in many scenarios.

The common way to explain recursion is by using the factorial calculation.

The factorial of a number is the number n multiplied by n-1, multiplied by n-2… and so on, until reaching the number 1:

3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
5! = 5 * 4 * 3 * 2 * 1 = 120

Using recursion we can write a function that calculates the factorial of any number:

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

print(factorial(3)) #   6
print(factorial(4)) #  24
print(factorial(5)) # 120

The base case

Every recursive function has two parts.

The base case is the condition that stops the recursion. In factorial(), that’s if n == 1: return 1.

The recursive case calls the function again, with a smaller input: factorial(n-1). Each call gets closer to the base case, until the chain of calls unwinds and returns the result.

Without a base case, the calls would never stop.

What happens when recursion doesn’t stop

If inside the factorial() function you call factorial(n) instead of factorial(n-1), you cause an infinite recursion. Python by default halts recursion at 1000 calls, and when this limit is reached you get a RecursionError:

RecursionError: maximum recursion depth exceeded

You can inspect the limit with the sys module:

import sys
print(sys.getrecursionlimit()) # 1000

A pitfall hiding in the example

The function above works for positive numbers. But try factorial(0) and you get a RecursionError.

Why? The base case checks n == 1. Starting from 0, that check never matches: the function calls factorial(-1), then factorial(-2), and so on, moving away from the base case until Python hits the limit.

The fix is a broader base case:

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

print(factorial(0)) # 1

This also happens to be mathematically correct, since the factorial of 0 is 1.

This is the thing to check in every recursive function you write: does every possible input eventually reach the base case?

When to reach for recursion

Recursion shines with nested data, where each level looks like the whole. Think of folders containing folders, or comments with replies that have replies. A function that processes one level and calls itself on the children is often the clearest way to walk the entire structure.