Python errors / RecursionError

RecursionError: maximum recursion depth exceeded

A function kept calling itself and never stopped. Python stops it after about 1,000 calls.

RecursionError: maximum recursion depth exceeded

Check these first

  1. A base case. A recursive function needs a case that returns without calling itself again.
  2. Getting closer. Each call has to move towards that case: a smaller number, a shorter list.
  3. Can it be skipped? if n == 0 is never true when n goes 5, 3, 1, -1. Compare with <= instead.

Causes and fixes

1 No base case

Without a case that stops it, the function calls itself until Python stops it. Add one, usually at the top.

Broken
def factorial(n):
    return n * factorial(n - 1)

print(factorial(5))
RecursionError: maximum recursion depth exceeded
Fixed
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))
120

2 A base case that's never reached

Counting down by 2 from 5 jumps over 0, so n == 0 is never true. A check with <= catches every way past it.

Broken
def countdown(n):
    if n == 0:
        return
    print(n)
    countdown(n - 2)

countdown(5)
RecursionError: maximum recursion depth exceeded
Fixed
def countdown(n):
    if n <= 0:
        return
    print(n)
    countdown(n - 2)

countdown(5)
5
3
1

Still stuck?