Recursion in Python

Some data repeats its own shape: a list that contains lists, a folder that contains folders. A function that calls itself matches that shape neatly. The recursion lesson in the fundamentals track explains base cases, recursive cases and tracing the call stack. Here you will write recursive functions in Python and meet the limits Python imposes.

A recursive function

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


print(factorial(5))
print(factorial(20))
print(factorial(30))

120
2432902008176640000
265252859812191058636308480000000

A function does not have to return a value. This one counts down by printing and calling itself:

def count_down(n):
    if n == 0:
        print("liftoff")
        return
    print(n)
    count_down(n - 1)


count_down(3)

3
2
1
liftoff

Both functions have the two required parts. The base case (n <= 1, n == 0) returns without calling again. The recursive case calls the function on a smaller problem. Python’s integers never overflow, so factorial(30) is exact, which is not true in many other languages.

Each call gets its own local n, so the calls do not interfere with each other. The scope lesson’s rule applies: every call runs in a fresh local scope.

The recursion limit

Every call that has not yet returned takes up space on the call stack. Python protects itself with a limit on that depth, 1000 by default. Exceed it and you get a RecursionError.

import sys

print(sys.getrecursionlimit())

1000

A function with no base case recurses until it hits the limit:

def count_down_forever(n):
    return count_down_forever(n - 1)


count_down_forever(10)

RecursionError: maximum recursion depth exceeded

count_down_forever above has no base case, so it recurses until the limit and Python raises RecursionError instead of crashing. That is the Python version of the stack overflow described in the fundamentals lesson. A missing or unreachable base case is by far the most common cause.

A correct function can hit the limit too, if it simply goes deeper than 1000 calls:

def total_to(n):
    if n == 0:
        return 0
    return n + total_to(n - 1)


print(total_to(5000))

RecursionError: maximum recursion depth exceeded

There are two fixes. Use a loop or sum(range(5001)), which needs no depth at all, or raise the limit with sys.setrecursionlimit:

import sys


def total_to(n):
    if n == 0:
        return 0
    return n + total_to(n - 1)


print(total_to(500))
print(sum(range(5001)))

sys.setrecursionlimit(10_000)
print(total_to(5000))

125250
12502500
12502500

Python also does not optimise tail calls. Some languages turn a recursive call in the last position into a jump, so it uses no extra stack. Python never does, so a “tail-recursive” function uses just as much depth as any other. In Python, a loop is the way to repeat something many thousands of times.

Recursion over nested data

Recursion earns its place when the data is nested to an unknown depth. The rule is: handle a plain item directly, and for a nested item call yourself.

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


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

21
0
10

The base case is hidden but present: an empty list has no items, so the loop never calls again. A for loop would need to know in advance how many levels to handle; recursion does not.

Walking a folder tree

A folder tree is nested data of the same sort: a folder holds files and other folders.

import shutil
import tempfile
from pathlib import Path


def walk(folder, depth=0):
    """Print a folder tree and return the number of files in it."""
    count = 0
    for entry in sorted(folder.iterdir(), key=lambda p: p.name.lower()):
        suffix = "/" if entry.is_dir() else ""
        print("  " * depth + entry.name + suffix)
        if entry.is_dir():
            count += walk(entry, depth + 1)
        else:
            count += 1
    return count


tmp = tempfile.mkdtemp()
root = Path(tmp) / "project"
(root / "src" / "pkg").mkdir(parents=True)
(root / "docs").mkdir()
for name in ["README.md", "src/main.py", "src/pkg/util.py", "docs/index.md"]:
    (root / name).write_text("x", encoding="utf-8")

print(root.name + "/")
files = walk(root, 1)
print("files:", files)

shutil.rmtree(tmp)

project/
  docs/
    index.md
  README.md
  src/
    main.py
    pkg/
      util.py
files: 4

The example builds its own small tree in a temporary folder so the output is the same everywhere, and shutil.rmtree deletes it at the end. walk prints each entry, indented by depth, and recurses into folders. The base case is a folder with nothing left to visit. In practice the standard library already walks trees for you, with os.walk, but writing it once by hand shows how it works.

When recursion is the wrong tool

Naive recursion can repeat work. The Fibonacci function calls itself twice, and the two calls recompute the same values over and over.

from functools import lru_cache

calls = 0


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


print(fib(20), calls)

calls = 0


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


print(fib_cached(20), calls)
print(fib_cached(90))

6765 21891
6765 21
2880067194370816120

Computing fib(20) takes 21,891 calls. With @lru_cache, which remembers results by argument, the body runs only 21 times, once per distinct value. The line @lru_cache(maxsize=None) above the def is a decorator, a way of wrapping a function; you do not need to understand how yet.

A good rule: use recursion for nested or branching data, and a loop for plain repetition.

Common pitfalls

• No base case, or one that is never reached. factorial(-1) is fine here because of n <= 1, but n == 1 alone would recurse forever for 0 or negatives.
• Not shrinking the problem. Calling f(n) from f(n) never ends. Each call must move toward the base case.
• Recursing a long way on a simple count. Depth above about a thousand raises RecursionError. Use a loop.
• Forgetting to return the recursive result. Writing factorial(n - 1) without return or without multiplying gives None or a wrong answer.
• Mutable default arguments in a recursive helper. An accumulator like result=[] is shared across calls, as the parameters lesson warned.
• Assuming tail calls are optimised. Python never does.

def deep_count(items):
    count = 0
    for item in items:
        if isinstance(item, list):
            count += deep_count(item)
        else:
            count += 1
    return count


def flatten(items):
    flat = []
    for item in items:
        if isinstance(item, list):
            flat.extend(flatten(item))
        else:
            flat.append(item)
    return flat


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

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

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


print(digit_sum(0))
print(digit_sum(7))
print(digit_sum(4921))

0
7
16

import shutil
import tempfile
from pathlib import Path


def count_by_extension(folder, counts=None):
    if counts is None:
        counts = {}
    for entry in folder.iterdir():
        if entry.is_dir():
            count_by_extension(entry, counts)
        else:
            counts[entry.suffix] = counts.get(entry.suffix, 0) + 1
    return counts


tmp = tempfile.mkdtemp()
root = Path(tmp) / "project"
(root / "src" / "pkg").mkdir(parents=True)
(root / "docs").mkdir()
for name in ["README.md", "src/main.py", "src/pkg/util.py", "docs/index.md"]:
    (root / name).write_text("x", encoding="utf-8")

result = count_by_extension(root)
print(dict(sorted(result.items())))

shutil.rmtree(tmp)

{'.md': 2, '.py': 2}

Summary

• A recursive function needs a base case and a recursive case that moves toward it.
• Python limits recursion depth (1000 by default) and raises RecursionError; it does not optimise tail calls, so use loops for long repetition.
• Recursion suits nested data such as lists of lists and folder trees; functools.lru_cache removes repeated work.

Next: type hints, which document what your functions expect and return.