Python Recursion: Base Cases, Stack Depth, and When Iteration Is Better

Recursion is a technique where a function calls itself with a smaller version of the same problem, until the problem becomes trivial enough to solve directly. It is not a magic trick — it is a particular way of expressing repetition, one that fits certain problem shapes very naturally.

The Two Parts of Every Recursive Function

Every recursive function needs exactly two things:

A base case — a condition where the function returns without calling itself. Without it, the recursion continues until Python hits its stack limit.
A recursive case — a call to the same function with a simpler or smaller input that moves toward the base case.

def factorial(n):
    # Base case: factorial(0) and factorial(1) are both 1
    if n <= 1:
        return 1
    # Recursive case: n! = n × (n-1)!
    return n * factorial(n - 1)

print(factorial(5))   # 120
print(factorial(0))   # 1

Tracing factorial(4):

factorial(4) = 4 × factorial(3)
                   = 4 × 3 × factorial(2)
                            = 4 × 3 × 2 × factorial(1)
                                              = 4 × 3 × 2 × 1
                                              = 24

Each call waits on the stack until the base case returns, then the chain unwinds and multiplies.

Fibonacci: Where Recursion Gets Expensive

The Fibonacci sequence is a classic recursion example, but also a demonstration of its main weakness.

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

print(fib(10))   # 55

This is elegant, but fib(30) is noticeably slow and fib(50) may not finish in a reasonable time. The function recomputes the same values repeatedly: fib(30) calls fib(29) and fib(28), and fib(29) also calls fib(28) — the same fib(28) is computed twice from two different call paths.

The fix is memoisation: cache results so each subproblem is solved only once.

from functools import lru_cache

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

print(fib_fast(100))   # 354224848179261915075 — instant

@lru_cache stores the result of each call. The second time fib_fast(28) is needed, it is returned from the cache without recursing.

Recursion for Tree and Hierarchical Data

Recursion is a natural fit when the data structure is itself hierarchical.

def count_files(path):
    """Count all files in a directory tree."""
    import os
    count = 0
    for entry in os.scandir(path):
        if entry.is_file():
            count += 1
        elif entry.is_dir():
            count += count_files(entry.path)   # recurse into subdirectory
    return count

# print(count_files("/home/user/documents"))

Each directory might contain files and other directories. The recursive call handles the nested directories without you needing to manage a stack manually.

# Flattening a nested list
def flatten(nested):
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))   # recurse for nested lists
        else:
            result.append(item)
    return result

print(flatten([1, [2, [3, 4], 5], 6, [7, 8]]))
# [1, 2, 3, 4, 5, 6, 7, 8]

The alternative — iterative tree traversal — requires explicitly managing a stack. The recursive version is shorter and matches the shape of the problem.

Python’s Recursion Limit

Python limits the call stack depth to prevent runaway recursion from consuming all memory. The default limit is 1,000 calls.

import sys
print(sys.getrecursionlimit())   # 1000

# Deep recursion raises RecursionError
def count_down(n):
    if n <= 0:
        return 0
    return 1 + count_down(n - 1)

# count_down(2000)   # RecursionError: maximum recursion depth exceeded

You can raise the limit:

sys.setrecursionlimit(5000)

But this is a workaround, not a solution. If you need recursion depth beyond the default, consider an iterative approach or a different algorithm.

Tail Recursion: Python Does Not Optimise It

In languages like Scheme or Haskell, a function where the recursive call is the last operation (tail recursion) is optimised to use constant stack space. Python does not perform this optimisation by design — Guido van Rossum has explicitly stated it is not a Python feature.

def factorial_tail(n, accumulator=1):
    # Tail-recursive form: recursive call is the only thing left to do
    if n <= 1:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)

# Still hits the recursion limit at depth 1000 in Python
# The tail form does not help here

If you need large inputs, convert to iteration.

Recursion vs Iteration: Choosing the Right Tool

	Recursion	Iteration
Code length	Often shorter for tree problems	Shorter for linear sequences
Readability	Matches hierarchical problems well	Easier to reason about for flat loops
Performance	Call stack overhead per level	No stack overhead
Stack depth	Limited by Python’s recursion limit	Unlimited
Debugging	Can be harder to trace	Easier to print state

Choose recursion when:

The problem is naturally defined recursively (trees, graphs, mathematical induction).
The recursive version is significantly clearer than the iterative version.
The input depth is bounded and well below the recursion limit.

Choose iteration when:

The problem is a linear sequence (list processing, range operations).
The depth could be large or unbounded.
Performance is critical (function call overhead adds up).

Converting Recursion to Iteration

For production code where recursion depth matters, you can simulate the call stack manually.

# Recursive flatten
def flatten_recursive(nested):
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten_recursive(item))
        else:
            result.append(item)
    return result

# Iterative flatten using an explicit stack
def flatten_iterative(nested):
    result = []
    stack = list(nested)[::-1]   # reversed so first item is at the end
    while stack:
        item = stack.pop()
        if isinstance(item, list):
            stack.extend(reversed(item))
        else:
            result.append(item)
    return result

print(flatten_iterative([1, [2, [3, 4], 5], 6]))
# [1, 2, 3, 4, 5, 6]

The iterative version uses a list as an explicit stack, removing Python’s call stack from the picture entirely.

Common Mistakes

Missing the base case. The function calls itself forever until RecursionError.

Base case that is never reached. If each recursive call does not actually get closer to the base case, the recursion is infinite.

Wrong return. Forgetting to return the recursive call is a silent bug — the function computes correctly but returns None to the caller:

def factorial(n):
    if n <= 1:
        return 1
    n * factorial(n - 1)   # Bug: result computed but not returned
    # Add: return n * factorial(n - 1)

Recomputing the same subproblems. For problems with overlapping subproblems (like Fibonacci), use memoisation or dynamic programming.