Python Recursion: Limits, Optimization, and Iterative Alternatives

Introduction

Python sets a default recursion depth limit of 1000 to prevent infinite recursion from crashing the interpreter with a stack overflow. While you can raise this limit, the better approach is usually to understand why the limit exists and how to write recursion that doesn’t hit it — or convert to an iterative solution when needed. See Python Guide for more context. See Python Guide for more context. See Python Guide for more context.

The Default Recursion Limit

import sys

print(sys.getrecursionlimit())  # => 1000

When you exceed this limit, Python raises RecursionError:

def count_down(n):
    return count_down(n - 1)  # infinite recursion

count_down(0)
# RecursionError: maximum recursion depth exceeded

Changing the Recursion Limit

You can increase the limit with sys.setrecursionlimit():

import sys

sys.setrecursionlimit(5000)
print(sys.getrecursionlimit())  # => 5000

When this is appropriate:

You have a well-bounded recursion that you know won’t go infinite
You’re processing deeply nested data structures (e.g., deeply nested JSON, ASTs)
You’ve verified the maximum depth your input can produce

When to be cautious:

Each stack frame uses memory — very deep recursion can exhaust RAM
The actual stack size limit is set by the OS, not just Python; hitting it causes a hard crash (segfault), not a clean RecursionError
Setting it to millions is dangerous

import sys
import resource

# Check the OS stack size limit (bytes)
soft, hard = resource.getrlimit(resource.RLIMIT_STACK)
print(f"Stack limit: {soft / 1024 / 1024:.1f} MB")

# A rough safe maximum for recursion depth
# Each frame is ~1KB, so 8MB stack → ~8000 frames
sys.setrecursionlimit(5000)  # conservative for most systems

Common Recursion Patterns

Factorial

# Recursive — hits limit at ~1000
def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)

# Iterative — no limit
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# Python built-in (best option)
import math
math.factorial(10000)  # works fine

Fibonacci

# Naive recursive — O(2^n), hits limit quickly
def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)

# With memoization — O(n) time, but still limited by depth
from functools import lru_cache

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

# Iterative — O(n) time, O(1) space, no depth limit
def fib_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

print(fib_iterative(10000))  # works fine

Converting Recursion to Iteration

The general technique is to use an explicit stack (a list) to simulate the call stack:

Tree Traversal

class Node:
    def __init__(self, val, left=None, right=None):
        self.val   = val
        self.left  = left
        self.right = right

# Recursive DFS — limited by tree depth
def dfs_recursive(node):
    if node is None:
        return []
    return [node.val] + dfs_recursive(node.left) + dfs_recursive(node.right)

# Iterative DFS — no depth limit
def dfs_iterative(root):
    if root is None:
        return []

    result = []
    stack  = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result

Flatten Nested Lists

# Recursive — fails on deeply nested input
def flatten_recursive(lst):
    result = []
    for item in lst:
        if isinstance(item, list):
            result.extend(flatten_recursive(item))
        else:
            result.append(item)
    return result

# Iterative — handles any depth
def flatten_iterative(lst):
    result = []
    stack  = list(lst)

    while stack:
        item = stack.pop()
        if isinstance(item, list):
            stack.extend(item)
        else:
            result.append(item)

    return result[::-1]  # reverse to restore order

nested = [1, [2, [3, [4, [5]]]]]
print(flatten_iterative(nested))  # => [1, 2, 3, 4, 5]

Directory Traversal

import os
from pathlib import Path

# Iterative directory walk — handles deeply nested directories
def find_files(root, extension='.py'):
    found = []
    stack = [Path(root)]

    while stack:
        current = stack.pop()
        for item in current.iterdir():
            if item.is_dir():
                stack.append(item)
            elif item.suffix == extension:
                found.append(item)

    return found

# Or just use os.walk (already iterative)
for dirpath, dirnames, filenames in os.walk('/some/path'):
    for filename in filenames:
        if filename.endswith('.py'):
            print(os.path.join(dirpath, filename))

Tail Call Optimization (TCO)

Python does not implement tail call optimization. In languages like Scheme or Haskell, a tail-recursive function (where the recursive call is the last operation) is automatically converted to a loop. Python doesn’t do this — every recursive call adds a frame to the stack regardless.

# This looks like tail recursion, but Python still uses stack frames
def sum_tail(n, accumulator=0):
    if n == 0:
        return accumulator
    return sum_tail(n - 1, accumulator + n)  # tail call — but Python doesn't optimize it

sum_tail(999)   # OK
sum_tail(1001)  # RecursionError

You can simulate TCO with a trampoline:

def trampoline(f):
    """Decorator that enables tail-call optimization via trampolining."""
    def wrapper(*args, **kwargs):
        result = f(*args, **kwargs)
        while callable(result):
            result = result()
        return result
    return wrapper

@trampoline
def sum_trampoline(n, acc=0):
    if n == 0:
        return acc
    return lambda: sum_trampoline(n - 1, acc + n)  # return a thunk instead of calling

print(sum_trampoline(100000))  # works without hitting recursion limit

When to Use Recursion vs Iteration

Scenario	Recommendation
Tree/graph traversal	Recursion is natural; convert to iterative for deep trees
Divide and conquer (merge sort, quicksort)	Recursion is clean; depth is O(log n) — usually fine
Fibonacci, factorial	Use iterative or `math.factorial`
Deeply nested data (depth > 500)	Use iterative with explicit stack
Mutual recursion	Consider converting to state machine
Simple, bounded depth	Recursion is fine and more readable

Practical Checklist

Know your maximum recursion depth for the given input
Use @lru_cache or @functools.cache to avoid redundant calls
For depth > 500, consider iterative conversion
Never set setrecursionlimit to millions — use iteration instead
Use os.walk or pathlib for file system traversal (already iterative)
For production code processing user input, always bound the recursion depth

Python Recursion: Limits, Optimization, and Iterative Alternatives

Introduction

The Default Recursion Limit

Changing the Recursion Limit

Common Recursion Patterns

Factorial

Fibonacci

Converting Recursion to Iteration

Tree Traversal

Flatten Nested Lists

Directory Traversal

Tail Call Optimization (TCO)

When to Use Recursion vs Iteration

Practical Checklist

Resources

Comments

Share this article

👍 Was this article helpful?