Recursion in Python

python recursion is one of those concepts that clicks slowly and then suddenly makes complete sense — a function that solves a problem by calling itself on a smaller version of that same problem. This article builds the concept up from a simple example, through the classic factorial and Fibonacci cases, into the practical limits Python imposes and how to work around inefficiency with memoization.

What Is Recursion?

Recursion is a technique where a function calls itself in order to break a problem down into smaller, structurally similar subproblems.

The two essential parts

Every recursive function needs exactly two things to work correctly:

• A base case — a condition that stops the recursion, returning a direct answer without any further recursive calls.

• A recursive case — the part where the function calls itself, but with input that's genuinely closer to the base case than before.

Miss either of these, and the function either never actually recurses (defeating the point) or never stops (covered in Section 3).

A simple starter example

Before tackling anything math-heavy, here's a countdown function that builds the basic intuition:

def countdown(n):
    if n <= 0:              # base case — stop here
        print("Liftoff!")
        return
    print(n)
    countdown(n - 1)        # recursive case — calls itself with a smaller number

countdown(3)
# 3
# 2
# 1
# Liftoff!

Each call to countdown either hits the base case (n <= 0) and stops, or makes a recursive call with a smaller value of n — moving measurably closer to that base case every time.

Classic Examples: Factorial and Fibonacci

Factorial, step by step

Factorial (written n!) is the classic first recursion example, and it maps naturally onto recursive thinking: n! is just n multiplied by (n-1)!, all the way down to 0! = 1.

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

print(factorial(5))   # 120

Walking through what actually happens internally as calls stack up:

factorial(5)
= 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * (1 * factorial(0)))))
= 5 * (4 * (3 * (2 * (1 * 1))))
= 120

Each call pauses, waiting on the result of the next call down, until factorial(0) finally hits the base case and returns 1 directly — at which point the whole stack of waiting calls unwinds, multiplying its way back up to the final answer.

Fibonacci: two recursive calls instead of one

The Fibonacci sequence — where each number is the sum of the two preceding ones — is a step up in complexity, since it requires two recursive calls per step rather than one:

def fibonacci(n):
    if n <= 1:                                  # base case
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)  # recursive case — two calls

print(fibonacci(6))   # 8

Why Fibonacci exposes recursion's downside

This naive version has a real, significant problem: it recalculates the same values over and over. fibonacci(6) calls fibonacci(5) and fibonacci(4) — but fibonacci(5) also calls fibonacci(4) internally, completely redundantly. As n grows, the number of these repeated, wasted calculations grows exponentially:

# fibonacci(5) internally recalculates fibonacci(3) TWICE,
# fibonacci(2) THREE times, and so on — massive redundant work

For small inputs, this redundancy is invisible. But fibonacci(35) or higher becomes noticeably, sometimes painfully slow, purely because of this repeated recalculation — not because the underlying math is actually that expensive. Section 4 covers the fix.

Python's Recursion Limit and RecursionError

The default recursion depth limit

Python imposes a limit on how deep a chain of recursive calls can go — by default, roughly 1,000 calls. You can check the current limit directly:

import sys
print(sys.getrecursionlimit())   # 1000, on most systems by default

What causes RecursionError

If a recursive function exceeds this limit — almost always because of a missing or unreachable base case — Python raises a RecursionError:

def broken_countdown(n):
    print(n)
    broken_countdown(n - 1)   # no base case — this never stops!

broken_countdown(5)
# ... prints many numbers, then eventually:
# RecursionError: maximum recursion depth exceeded

If you ever see this error, the first thing to check is almost always your base case: does it exist at all, and — just as important — is it actually reachable given how the recursive case modifies its input on each call? A base case that checks for a condition the recursive case can never actually produce is functionally the same as having no base case at all.

Raising the limit — a last resort, not a fix

sys.setrecursionlimit() lets you raise this ceiling manually:

import sys
sys.setrecursionlimit(3000)

This is worth treating with real caution. It's not a fix for a broken recursive function — if your recursion is hitting the limit because of a genuine bug (an unreachable base case), raising the limit just delays the eventual RecursionError, or worse, risks crashing the Python interpreter itself with a segmentation fault once you push the limit high enough, since each level of recursion consumes real memory on the call stack. Only raise this limit deliberately, for a recursive algorithm you're confident is correct and genuinely needs more depth than the default allows — never as a quick patch for a suspected bug.

Python deliberately skips tail-call optimization

If you've used certain other languages, you might expect "tail recursion" (where the recursive call is the very last operation in a function) to be automatically optimized to avoid growing the call stack at all. Python deliberately does not do this. This is an intentional design decision by Python's creators, prioritizing clear, debuggable tracebacks — showing you the full chain of calls when something goes wrong — over the performance and memory benefit tail-call optimization would provide. Practically, this means you can't rely on restructuring a recursive function into tail-recursive form to sidestep Python's recursion limit; the limit applies regardless of how the recursive call is structured.

Making Recursion Efficient: Memoization

The problem, restated

As shown in Section 2, naive recursive Fibonacci recalculates the same values repeatedly, leading to genuinely exponential time complexity — the amount of work roughly doubles with each additional step of n, making it impractical for anything beyond fairly small inputs.

The fix: functools.lru_cache

Python's functools module provides lru_cache, a decorator that automatically caches a function's results, keyed by its arguments — if the same arguments come in again, the cached result is returned instantly instead of recalculating from scratch.

from functools import lru_cache

@lru_cache
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(35))   # fast — near-instant, instead of taking several seconds

That single @lru_cache decorator transforms this function's performance from exponential time down to near-linear time — every distinct value of n only ever gets computed once, no matter how many times it's needed across the whole call tree.

Before and after, illustrated

import time

# Without caching
def fib_slow(n):
    if n <= 1:
        return n
    return fib_slow(n - 1) + fib_slow(n - 2)

start = time.time()
fib_slow(30)
print(f"Without cache: {time.time() - start:.4f} seconds")

# With caching
@lru_cache
def fib_fast(n):
    if n <= 1:
        return n
    return fib_fast(n - 1) + fib_fast(n - 2)

start = time.time()
fib_fast(30)
print(f"With cache: {time.time() - start:.4f} seconds")

Running something like this yourself makes the difference dramatic and immediately obvious — the cached version finishes essentially instantly, while the uncached version takes a noticeably longer, measurable amount of time even at a relatively modest value of n.

Recursion vs. Iteration: When to Choose Each

Where recursion is the natural fit

Recursion genuinely shines for problems with an inherently recursive structure — where the problem itself is naturally defined in terms of smaller versions of itself. This includes traversing trees and graphs (where each node's subtree is itself a smaller tree), navigating nested data structures of unknown depth (as touched on in the earlier nested lists/dictionaries article), and divide-and-conquer algorithms like quicksort or binary search, where the core strategy is explicitly "solve a smaller version of this same problem, then combine the results."

Where iteration has the advantage

Iteration (a plain loop) has no recursion depth limit to worry about, and for simple, linear repetition, it's typically both faster and more memory-efficient than the equivalent recursive version, since it doesn't need to maintain a growing call stack.

# Factorial rewritten as a loop — no recursion depth concerns at all
def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

print(factorial_iterative(5))   # 120

For something like factorial or a simple linear Fibonacci calculation, the iterative version is often genuinely the more practical choice in real code — recursion is elegant and conceptually clear for these examples, but not strictly necessary.

A practical debugging checklist

When a recursive function isn't behaving as expected, work through these in order:

1. Verify the base case is reachable. Trace through the recursive case by hand and confirm it can actually produce the exact condition your base case checks for.

2. Confirm each call makes real progress toward the base case. Every recursive call should move measurably closer to the base case — a smaller number, a shorter list, a smaller subtree. If a call could plausibly pass through with input unchanged (or moving further from the base case), that's the source of an infinite recursion.

3. Test with small inputs first. Before trusting a recursive function on large or complex input, verify it manually against the smallest meaningful cases — factorial(0), factorial(1) — where you can trace the entire call chain by hand and confirm it matches your expectations exactly.