RecursionError Examples

Short, runnable programs that show python recursionerror in action. Read the explanation, press Run, then change the code and try your own ideas. New to the topic? Start with the Python RecursionError lesson.

1Fibonacci with a cache

Without a cache, fib makes an explosion of repeated calls. functools.cache remembers results, so each value is computed once. The recursion is still as deep as n.

Fibonacci with a cache

from functools import cache

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

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

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

2Safe recursive folder sizes

Real tree data (folders inside folders) is a natural fit for recursion because it is shallow in practice.

Safe recursive folder sizes

folder = {"name": "photos", "size": 2, "children": [
    {"name": "2023", "size": 5, "children": []},
    {"name": "2024", "size": 3, "children": [
        {"name": "trip", "size": 10, "children": []}]}]}

def total_size(node):
    return node["size"] + sum(total_size(c) for c in node["children"])

print(total_size(folder))

Expected output20

3Binary search that stops

Each call halves the search range, so the base cases (empty range or a match) are always reached after about log2(n) calls.

Binary search that stops

def find(items, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if items[mid] == target:
        return mid
    if items[mid] < target:
        return find(items, target, mid + 1, high)
    return find(items, target, low, mid - 1)

prices = [3, 8, 15, 22, 40, 57]
print(find(prices, 22, 0, len(prices) - 1))
print(find(prices, 9, 0, len(prices) - 1))

Expected output3
-1

4Counting down with a loop

Anything that runs once per item of a long sequence is usually clearer, and safer, as a loop.

Counting down with a loop

def countdown(n):
    result = []
    while n > 0:
        result.append(n)
        n -= 1
    return result

print(countdown(5))
print(len(countdown(5000)))

Expected output[5, 4, 3, 2, 1]
5000

5Catching RecursionError

You can catch RecursionError like any other exception, for example to report that input is too deeply nested.

Catching RecursionError

import sys

def depth(value):
    return 1 + max((depth(v) for v in value), default=0) if isinstance(value, list) else 0

deep = []
for _ in range(500):
    deep = [deep]

sys.setrecursionlimit(150)
try:
    depth(deep)
except RecursionError:
    print("input is nested too deeply")
finally:
    sys.setrecursionlimit(1000)

Expected outputinput is nested too deeply

Practise next

Python RecursionError exercises → Back to the lesson

Python while Loops examples Python Functions examples Python Recursion examples Python Exceptions: try, except, else and finally examples