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
- Base case: returns directly for the smallest instance.
- Progress measure: every recursive call moves strictly toward a base case.
- Inductive contract: assume recursive results are correct, then combine them correctly for the current instance.
- 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 guarantee tail-call elimination; CPython does not implement tail-call optimization of Python functions. Its recursion limit protects against stack overflow. 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.
A complete tree example and its assumptions
Here None represents an empty subtree. Every other node must have left and
right attributes. The structure must be a finite tree: no cycles and no node
shared between branches if the goal is to count distinct nodes.
from dataclasses import dataclass
@dataclass
class Node:
left: "Node | None" = None
right: "Node | None" = None
tree = Node(Node(), Node(Node()))
assert tree_size(None) == 0
assert tree_size(Node()) == 1
assert tree_size(tree) == 4
Each leaf returns 1 + 0 + 0; its parent adds the sizes of the two disjoint
subtrees plus one for itself. The number of nodes in the current subtree is a
nonnegative integer that strictly decreases on each nonempty descent. This
justifies termination, not merely the presence of a base-case branch.
For a tree with n nodes and height h, work is linear in n and peak recursive
stack usage is linear in h, assuming constant-time attribute access and counting
integer additions as constant-time operations.
The same contract can avoid recursive calls:
def tree_size_iterative(node):
pending = [] if node is None else [node]
count = 0
while pending:
current = pending.pop()
count += 1
if current.right is not None:
pending.append(current.right)
if current.left is not None:
pending.append(current.left)
return count
assert tree_size_iterative(tree) == tree_size(tree)
assert tree_size_iterative(None) == 0
Neither version detects cycles. A graph traversal needs a visited set and an
explicit definition of whether shared nodes count once. In CPython, excessive
recursive depth raises RecursionError; the exact safe depth is not portable.
The sys documentation
warns that setting the recursion limit too high can crash the interpreter.
Memoization reduces repeated work, not the deepest chain of calls.
Run the complete tree_size example in Python Tutor and pause at a None subtree. Follow its return value into the waiting parent frame, then count the deepest set of simultaneously active frames rather than all calls made during the run.