Skip to main content

Recursion in Python

A recursive function solves an instance using results from smaller instances of the same problem.

def tree_size(node) -> int:
    if node is None:
        return 0
    return 1 + tree_size(node.left) + tree_size(node.right)

Correctness checklist​

  1. Base case: returns directly for the smallest instance.
  2. Progress measure: every recursive call moves strictly toward a base case.
  3. Inductive contract: assume recursive results are correct, then combine them correctly for the current instance.
  4. State ownership: mutable accumulators are copied, restored, or otherwise scoped deliberately.

Cost model​

Count both the number of calls and work per call. Peak stack space depends on maximum active depth, not the total number of nodes in the recursion tree.

Python does not perform tail-call elimination as a general language guarantee, and the interpreter limits recursion depth to protect the process stack. Deep linear recursion should usually become iteration with an explicit stack.

When recursion fits​

  • trees and nested syntax;
  • divide-and-conquer algorithms;
  • depth-first search and backtracking;
  • naturally recursive mathematical definitions when input depth is controlled.

Repeated subproblems​

Recursion alone does not imply inefficiency, but overlapping calls can cause exponential repetition. functools.cache or lru_cache can memoize pure calls with hashable arguments; caches retain argument and result references and need an explicit lifetime policy in long-running processes.

Do not cache side-effectful, time-dependent, random, generator, or mutable-result functions merely because they are recursive.

Sources​