Recursion in Python: A Complete Guide with Examples

Recursion in Python is when a function calls itself to solve a smaller version of the same problem. Every recursive function needs a base case that stops the calls and a recursive case that moves toward it; without a base case Python stops with RecursionError after about 1,000 calls. This guide shows how Python recursion works on the call stack, the recursion limit, how memoization with lru_cache makes recursive functions fast, practical examples (nested lists, folders, binary search, permutations) and when a loop is the better choice, with every example run and its real output.

All examples were run with Python 3.12.5 and Matplotlib 3.11.2 in the Windows Command Prompt. Reference: sys.getrecursionlimit() and functools.lru_cache in the Python docs.

A simple recursive function

def countdown(n):
    if n == 0:                  # base case: stop here
        print("Liftoff!")
        return
    print(n)
    countdown(n - 1)            # recursive case: a smaller problem

countdown(3)


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

print("5! =", factorial(5))

Output:

3
2
1
Liftoff!
5! = 120

countdown(3) prints 3 and calls countdown(2), which calls countdown(1), and so on until n == 0, the base case. factorial() works the same way but combines the results on the way back: 5 × 4 × 3 × 2 × 1.

How recursion works: the call stack

Each call gets its own frame on the call stack with its own n. The calls go down until the base case, then each one returns to the call that made it. This version prints every step:

def factorial(n, depth=0):
    indent = "    " * depth
    print(f"{indent}factorial({n}) called")
    if n <= 1:
        print(f"{indent}factorial({n}) returns 1   <- base case")
        return 1
    result = n * factorial(n - 1, depth + 1)
    print(f"{indent}factorial({n}) returns {n} * factorial({n - 1}) = {result}")
    return result

factorial(4)

Output:

factorial(4) called
    factorial(3) called
        factorial(2) called
            factorial(1) called
            factorial(1) returns 1   <- base case
        factorial(2) returns 2 * factorial(1) = 2
    factorial(3) returns 3 * factorial(2) = 6
factorial(4) returns 4 * factorial(3) = 24

Base case, recursion limit and RecursionError

Python limits the depth of the call stack to protect itself. Forgetting the base case, or recursing on very large inputs, raises RecursionError:

import sys

print("recursion limit:", sys.getrecursionlimit())

def depth(n):
    return depth(n + 1)              # no base case

try:
    depth(0)
except RecursionError as e:
    print("RecursionError:", e)

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

print(sum_to(900))                   # fine
try:
    sum_to(5000)                     # deeper than the limit
except RecursionError as e:
    print("sum_to(5000) -> RecursionError:", e)

Output:

recursion limit: 1000
RecursionError: maximum recursion depth exceeded
405450
sum_to(5000) -> RecursionError: maximum recursion depth exceeded

sys.setrecursionlimit() can raise the limit, but each frame uses real stack memory and a very high limit can crash the interpreter. If your input can be deep, use a loop instead (see below).

Make recursion fast with memoization

The plain recursive Fibonacci function computes the same values again and again: fib(30) makes over a million calls. functools.lru_cache stores each result the first time, so every value is computed once:

from functools import lru_cache

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

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

for n in (10, 20, 30):
    calls = 0
    value = fib(n)
    fib_memo.cache_clear()
    fib_memo(n)
    print(f"fib({n}) = {value:>6}   plain recursion: {calls:>9,} calls   memoized: {fib_memo.cache_info().misses} calls")

Output:

fib(10) =     55   plain recursion:       177 calls   memoized: 11 calls
fib(20) =   6765   plain recursion:    21,891 calls   memoized: 21 calls
fib(30) = 832040   plain recursion: 2,692,537 calls   memoized: 31 calls

The same comparison as a chart, including a plain for loop:

import time
from functools import lru_cache
import matplotlib.pyplot as plt

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

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

def fib_loop(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

ns = list(range(5, 29))
def timed(func, n, clear=False):
    if clear:
        fib_memo.cache_clear()
    t = time.perf_counter()
    func(n)
    return (time.perf_counter() - t) * 1000

plain = [timed(fib, n) for n in ns]
memo = [timed(fib_memo, n, clear=True) for n in ns]
loop = [timed(fib_loop, n) for n in ns]

plt.figure(figsize=(8, 4.8))
plt.plot(ns, plain, "o-", label="plain recursion")
plt.plot(ns, memo, "s-", label="recursion + lru_cache")
plt.plot(ns, loop, "^-", label="for loop")
plt.yscale("log")
plt.xlabel("n")
plt.ylabel("time (ms, log scale)")
plt.title("Fibonacci: plain recursion vs memoization vs loop")
plt.legend()
plt.grid(True, which="both", alpha=0.3)
plt.tight_layout()
plt.show()
print(f"n=28: plain {plain[-1]:.1f} ms, memoized {memo[-1]:.3f} ms, loop {loop[-1]:.3f} ms")

Output:

n=28: plain 32.5 ms, memoized 0.004 ms, loop 0.001 ms

More ways to write it in Fibonacci series in Python.

Recursion with nested data: lists inside lists

Recursion fits data that contains smaller copies of itself. A list that can contain lists at any depth is summed and flattened like this:

def total(items):
    """Sum numbers in a list that can contain lists, at any depth."""
    result = 0
    for item in items:
        if isinstance(item, list):
            result += total(item)       # recurse into the sub-list
        else:
            result += item
    return result

def flatten(items):
    for item in items:
        if isinstance(item, list):
            yield from flatten(item)
        else:
            yield item

data = [1, [2, 3], [4, [5, [6, 7]]], 8]
print(total(data))
print(list(flatten(data)))

Output:

36
[1, 2, 3, 4, 5, 6, 7, 8]

Recursion with folders: print a directory tree

Folders contain folders, so walking them is naturally recursive:

from pathlib import Path

# build a small folder tree to walk
root = Path("project")
for f in ["README.md", "src/app.py", "src/utils/io.py", "src/utils/text.py", "tests/test_app.py"]:
    (root / f).parent.mkdir(parents=True, exist_ok=True)
    (root / f).write_text("x" * 100)

def show(folder, prefix=""):
    entries = sorted(folder.iterdir(), key=lambda p: (p.is_file(), p.name))
    for i, entry in enumerate(entries):
        last = i == len(entries) - 1
        print(prefix + ("└── " if last else "├── ") + entry.name)
        if entry.is_dir():
            show(entry, prefix + ("    " if last else "│   "))   # recurse into the sub-folder

def folder_size(folder):
    return sum(folder_size(p) if p.is_dir() else p.stat().st_size for p in folder.iterdir())

print(root.name)
show(root)
print("total size:", folder_size(root), "bytes")

Output:

project
├── src
│   ├── utils
│   │   ├── io.py
│   │   └── text.py
│   └── app.py
├── tests
│   └── test_app.py
└── README.md
total size: 500 bytes

For everyday file listing, Path.rglob() and os.walk() already do the recursion for you: see list files in a directory with Python.

Classic recursive algorithms

def binary_search(items, target, low=0, high=None):
    if high is None:
        high = len(items) - 1
    if low > high:
        return -1                                   # base case: not found
    mid = (low + high) // 2
    if items[mid] == target:
        return mid                                  # base case: found
    if items[mid] < target:
        return binary_search(items, target, mid + 1, high)
    return binary_search(items, target, low, mid - 1)

def permutations(s):
    if len(s) <= 1:
        return [s]
    return [ch + rest for i, ch in enumerate(s) for rest in permutations(s[:i] + s[i + 1:])]

def power(x, n):
    """x**n with O(log n) multiplications."""
    if n == 0:
        return 1
    half = power(x, n // 2)
    return half * half * (x if n % 2 else 1)

def reverse(s):
    return s if len(s) <= 1 else reverse(s[1:]) + s[0]

print(binary_search([3, 8, 15, 23, 42, 57, 91], 42))
print(permutations("abc"))
print(power(2, 30), 2 ** 30)
print(reverse("recursion"))

Output:

4
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
1073741824 1073741824
noisrucer

Step-by-step programs: binary search in Python (recursive and iterative), factorial of a number, reverse a string and Armstrong numbers.

Recursion vs iteration

Anything written recursively can be written with a loop. In Python the loop is usually faster and has no depth limit, and Python does not optimize tail calls, so even tail-recursive functions hit the limit:

import sys

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

def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_recursive(20) == factorial_loop(20))
print(len(str(factorial_loop(1500))), "digits in 1500! (loop, no depth limit)")
try:
    factorial_recursive(1500)
except RecursionError:
    print("factorial_recursive(1500) -> RecursionError")

# Python does not optimize tail calls: this still uses one stack frame per call
def count_down_tail(n):
    return n if n == 0 else count_down_tail(n - 1)
try:
    count_down_tail(sys.getrecursionlimit() + 10)
except RecursionError:
    print("tail-recursive version -> RecursionError too")

Output:

True
4115 digits in 1500! (loop, no depth limit)
factorial_recursive(1500) -> RecursionError
tail-recursive version -> RecursionError too

	Recursion	Iteration (loop)
Best for	Trees, nested data, divide and conquer, backtracking	Counting, sequences, simple repetition
Depth limit	About 1000 call