Recursive Functions

A recursive function calls itself. Python has a default recursion limit of about 1000, so deeply recursive algorithms must be written iteratively or with explicit stacks. For numerical recursion, prefer memoisation.

Recursion expresses problems whose structure repeats at smaller scale—trees, nested JSON, combinatorics. Python allows elegant recursive solutions but enforces a default recursion limit near 1000 frames, so deep linear recursion must become iteration or use trampolines.

Memoization with functools.lru_cache turns exponential recursive algorithms into polynomial time without changing the mathematical definition—essential for interview-style dynamic programming in production utilities.

Production code combines this topic with logging, tests, and clear module boundaries so refactors stay safe when requirements grow.

Base case returns a concrete answer without further calls; missing base case causes RecursionError.

sys.getrecursionlimit() reports the cap; sys.setrecursionlimit is rarely the right fix.

Tail recursion is not optimized in CPython; rewrite as while loops for depth.

Divide-and-conquer recursion (merge sort) uses logarithmic stack depth.

lru_cache on recursive defs caches subproblems automatically.

Explicit stacks simulate recursion for DFS on deep graphs.

When recursion depth tracks input size (linked list length), switch to iterative accumulation. For tree recursion, post-order vs pre-order determines whether you process children before parent—match your aggregation needs.

Mutual recursion between two functions works but hurts readability; merge into one function with a mode parameter when possible.

Iterative DFS with deque avoids C stack limits better than raising sys.setrecursionlimit on unknown depth graphs.

Explicit stack DFS handles deep graphs; recursion limit increases risk C stack overflow.

Read the parent tutorial on pythondeck.com for runnable snippets, then reproduce them locally in a virtual environment with pinned dependency versions matching your deployment target.

When pairing with teammates, agree on one idiomatic pattern per concern—mixed styles in one repo slow reviews and invite subtle integration bugs during merges.

Relying on recursion for 10**6 linear depth without iteration.

Forgetting lru_cache on overlapping subproblems in numeric recursion.

Printing in recursive paths on large trees, flooding stdout.

Mutating shared global tallies instead of returning values upward.

State the base case and progress measure in comments.

Profile recursive vs iterative versions on realistic input sizes.

Use recursion for trees; use loops for long chains.

Add tests at maximum expected depth plus one over-limit case.

Re-read the examples below with these ideas in mind; change variable names and inputs to match your own project.

# Example: Factorial
# Run in the REPL or save as a .py file and execute with python.
def fact(n):
    return 1 if n <= 1 else n * fact(n - 1)

print(fact(10))

# Example: Tree walk
# Run in the REPL or save as a .py file and execute with python.
tree = {"root": {"left": {"left": {}, "right": {}}, "right": {}}}

def count(node):
    return 1 + sum(count(child) for child in node.values())

print(count(tree))

# Example: Memoised recursion
# Run in the REPL or save as a .py file and execute with python.
from functools import lru_cache

@lru_cache(maxsize=None)
def paths(m, n):
    if m == 0 or n == 0: return 1
    return paths(m-1, n) + paths(m, n-1)

print(paths(15, 15))

# Base case stops recursion; recursive case moves toward base
def fact(n):  # factorial
    if n <= 1:  # base case
        return 1  # 0! and 1!
    return n * fact(n - 1)  # recursive step

print(fact(6))  # 720
def countdown(n):  # simple recursion
    if n == 0:  # base
        print("go")  # end
        return  # stop
    print(n)  # current
    countdown(n - 1)  # recurse
countdown(3)  # 3 2 1 go

# lru_cache avoids exponential recomputation in recursion
from functools import lru_cache  # cache

@lru_cache(maxsize=None)  # unbounded memo
def paths(m, n):  # grid paths
    if m == 0 or n == 0:  # edges
        return 1  # one way
    return paths(m - 1, n) + paths(m, n - 1)  # down + right

print(paths(10, 10))  # 184756
print(paths.cache_info().hits)  # many cache hits