Skip to content

python.recursive_no_base_case

Stability High

Detects recursive functions that may not have clear base case termination, risking stack overflow.

Why It Matters

Unbounded recursion causes:

Stack overflow — Python’s default recursion limit is ~1000
Service crashes — RecursionError terminates the process
Hard to debug — Stack traces can be massive
Resource exhaustion — Each call consumes stack space

Example

# ❌ Before (missing base case)
def process_tree(node):
    for child in node.children:
        process_tree(child)  # No termination condition!

def factorial(n):
    return n * factorial(n - 1)  # No check for n <= 0

# ✅ After (with base case)
def process_tree(node):
    if not node.children:  # Base case
        return
    for child in node.children:
        process_tree(child)

def factorial(n):
    if n <= 1:  # Base case
        return 1
    return n * factorial(n - 1)

What Unfault Detects

Recursive functions without clear return in base case
Missing termination conditions
Infinite recursion patterns
Mutual recursion without bounds

Auto-Fix

Unfault generates patches that add base case checks:

def traverse(node, depth=0, max_depth=100):
    if depth > max_depth:
        raise RecursionError(f"Max depth {max_depth} exceeded")
    if node is None:
        return
    # Process node
    traverse(node.left, depth + 1, max_depth)
    traverse(node.right, depth + 1, max_depth)

Iterative Alternatives

# Iterative tree traversal (no recursion limit)
def process_tree_iterative(root):
    stack = [root]
    while stack:
        node = stack.pop()
        process(node)
        stack.extend(node.children)

# Trampoline pattern for tail recursion
def trampoline(fn):
    def wrapper(*args):
        result = fn(*args)
        while callable(result):
            result = result()
        return result
    return wrapper