PythonRecursion

Recursion

Recursion is when a function calls itself to solve a smaller version of the same problem. Every correct recursive function needs two parts: a base case that stops the recursion, and a recursive case that makes progress toward that base case.

Base Case and Recursive Case

The classic first example is factorial: n! is n * (n-1)!, and the base case is 0! = 1. Every recursive call passes a smaller n, guaranteeing the base case is eventually reached.

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


print(factorial(5))   # 5 * 4 * 3 * 2 * 1
print(factorial(0))   # base case directly
120
1

Tracing factorial(3) shows the calls stacking up, then resolving back down once the base case is hit:

Python
factorial(3)
= 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * (2 * (1 * factorial(0)))
= 3 * (2 * (1 * 1))
= 6
A Second Example: Fibonacci

Fibonacci has two base cases (fib(0) = 0, fib(1) = 1) and a recursive case that calls itself twice.

Python
def fib(n):
    if n <= 1:                    # base cases
        return n
    return fib(n - 1) + fib(n - 2)  # recursive case


for i in range(10):
    print(fib(i), end=" ")
0 1 1 2 3 5 8 13 21 34
Warning
This naive `fib` recomputes the same values repeatedly — `fib(5)` calls `fib(3)` twice, `fib(2)` three times, and so on — making it exponentially slow for larger `n`. The fix, memoization, is covered below.
Python's Recursion Limit

Unlike loops, each recursive call adds a new frame to the call stack. Python limits how deep this can go — by default, around 1000 frames — to avoid crashing the interpreter with a stack overflow.

Python
import sys

print(sys.getrecursionlimit())  # 1000, by default


def count_down(n):
    if n <= 0:
        return
    count_down(n - 1)


count_down(2000)  # exceeds the default limit
1000
RecursionError: maximum recursion depth exceeded
Warning
`RecursionError` usually signals either a missing/incorrect base case (infinite recursion) or a problem that's simply too deep for recursion in Python. While `sys.setrecursionlimit(n)` can raise the ceiling, doing so risks crashing the entire Python process with a real stack overflow — it's rarely the right fix.
Python Does Not Optimize Tail Calls
Note
Some languages (like Scheme or Elixir) automatically detect when a recursive call is the very last operation in a function ("tail position") and reuse the current stack frame instead of adding a new one — this is called tail-call optimization (TCO). CPython deliberately does **not** implement TCO, even for tail-recursive functions, so every recursive call always consumes stack space, no matter how the function is written.

Python
# Even though this is written "tail-recursively", CPython gives it no special treatment
def sum_to(n, acc=0):
    if n == 0:
        return acc
    return sum_to(n - 1, acc + n)  # last operation, but still uses a new stack frame

print(sum_to(500))   # fine
print(sum_to(5000))  # RecursionError anyway — no TCO in CPython
125250
RecursionError: maximum recursion depth exceeded
When to Prefer Iteration Over Recursion

Because of the recursion limit and the lack of TCO, an equivalent loop is usually the safer and faster choice in Python whenever the recursion depth could be large.

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


print(factorial_iterative(1000))  # works fine, no stack concerns

Use recursion when...

Use iteration when...

The problem is naturally recursive (trees, nested structures, divide-and-conquer)

A simple loop expresses the logic just as clearly

The depth is small and bounded

The depth could be large or unbounded

Clarity matters more than raw performance

Performance or stack safety is a concern

Speeding Up Recursion with `functools.lru_cache`

Memoization means caching the result of a function call so repeated calls with the same arguments return instantly instead of recomputing. Python's standard library provides this as a one-line decorator.

Python
import functools


@functools.lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)


print(fib(35))  # near-instant, thanks to caching
print(fib.cache_info())
9227465
CacheInfo(hits=33, misses=36, maxsize=None, currsize=36)
Tip
`@functools.lru_cache` turns the exponential-time naive Fibonacci into a linear-time function with a single decorator line — each unique `n` is computed only once, then reused from the cache for every subsequent call with that same value.
Example
A recursive function to sum the digits of a number, with memoization added for repeated calls on the same input.

Python
import functools


@functools.lru_cache(maxsize=None)
def digit_sum(n):
    if n < 10:          # base case: single digit
        return n
    return n % 10 + digit_sum(n // 10)  # last digit + sum of the rest


print(digit_sum(9875))  # 9 + 8 + 7 + 5
print(digit_sum(123))
29
6