A recursive function solves a problem by calling itself on a smaller piece of it. Natural for trees, divide-and-conquer and backtracking — but in Python, mind the stack depth.

Anatomy

Python

def factorial(n: int) -> int:
    if n <= 1:                    # base case
        return 1
    return n * factorial(n - 1)   # recursive case: smaller input

def digit_sum(n: int) -> int:
    return n if n < 10 else n % 10 + digit_sum(n // 10)

print(factorial(5), factorial(20))   # 120 2432902008176640000
print(digit_sum(98765))              # 35

Define the base case
The smallest input you can answer directly (n <= 1, empty list, None node).
Trust the recursion
Assume the call on the smaller input returns the right answer.
Combine
Build this level's answer from the smaller result(s).
Check progress
Every call must shrink the input, or it never reaches the base case.

The call stack

Each call gets its own frame (its local variables) pushed on the call stack; it is popped when the call returns. factorial(4) stacks four frames before any multiplication happens.

Python

def countdown(n, depth=0):
    print("  " * depth + f"enter {n}")
    if n > 0:
        countdown(n - 1, depth + 1)
    print("  " * depth + f"leave {n}")

countdown(2)

Output

enter 2
  enter 1
    enter 0
    leave 0
  leave 1
leave 2

Recursion limit & RecursionError

CPython caps the stack depth (default 1000 frames) to avoid crashing the interpreter. Exceeding it raises RecursionError — also what you get from a missing base case.

Python

import sys

def no_base_case(n):
    return no_base_case(n + 1)

try:
    no_base_case(0)
except RecursionError as e:
    print(type(e).__name__, "-", e)   # RecursionError - maximum recursion depth exceeded
print(sys.getrecursionlimit())        # 1000

Option	When
Rewrite iteratively (loop / explicit stack)	Best fix for deep, linear recursion (linked lists, DFS on 10⁵ nodes)
`sys.setrecursionlimit(10**5)`	Quick fix in contests — the C stack may still overflow and crash
Memoize (`@cache`)	When the depth is fine but the number of calls explodes

Memoization: from exponential to linear

Python

from functools import cache

calls = 0
def fib_slow(n):
    global calls
    calls += 1
    return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)

fib_slow(20)
print(calls)                 # 21891   ← O(2^n) calls

@cache
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(90))               # 2880067194370816120
print(fib.cache_info().misses)   # 91   ← each n computed once

Recursion → iteration with an explicit stack

Python

tree = {"a": ["b", "c"], "b": ["d"], "c": [], "d": []}

def dfs_recursive(node, out):
    out.append(node)
    for child in tree[node]:
        dfs_recursive(child, out)
    return out

def dfs_iterative(root):
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node)
        stack.extend(reversed(tree[node]))   # reversed → same order as recursion
    return out

print(dfs_recursive("a", []))   # ['a', 'b', 'd', 'c']
print(dfs_iterative("a"))       # ['a', 'b', 'd', 'c']

Classic patterns

Python

def binary_search(xs, target, lo=0, hi=None):
    hi = len(xs) - 1 if hi is None else hi
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if xs[mid] == target:
        return mid
    if xs[mid] < target:
        return binary_search(xs, target, mid + 1, hi)
    return binary_search(xs, target, lo, mid - 1)

def power(x, n):                       # fast exponentiation: O(log n) calls
    if n == 0:
        return 1
    half = power(x, n // 2)
    return half * half * (x if n % 2 else 1)

def flatten(items):
    for it in items:
        if isinstance(it, list):
            yield from flatten(it)     # recursive generator
        else:
            yield it

print(binary_search([1, 3, 5, 7, 9], 7))     # 3
print(power(2, 30))                          # 1073741824
print(list(flatten([1, [2, [3, [4]], 5]])))  # [1, 2, 3, 4, 5]

Backtracking: subsets & permutations

Backtracking explores a tree of choices: choose, recurse, un-choose. It powers subsets, permutations, N-Queens, Sudoku and word search.

Python

def subsets(nums):
    result, path = [], []
    def backtrack(i):
        if i == len(nums):
            result.append(path[:])      # copy! path keeps changing
            return
        path.append(nums[i])            # choose nums[i]
        backtrack(i + 1)
        path.pop()                      # un-choose
        backtrack(i + 1)                # skip nums[i]
    backtrack(0)
    return result

def permutations(nums):
    if len(nums) <= 1:
        return [nums[:]]
    out = []
    for i, x in enumerate(nums):
        for rest in permutations(nums[:i] + nums[i + 1:]):
            out.append([x] + rest)
    return out

print(subsets([1, 2]))          # [[1, 2], [1], [2], []]
print(permutations([1, 2, 3]))  # [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Trees & mutual recursion

Python

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

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

def inorder(node):
    return inorder(node.left) + [node.val] + inorder(node.right) if node else []

root = Node(2, Node(1), Node(4, Node(3)))
print(height(root), inorder(root))    # 3 [1, 2, 3, 4]

def is_even(n):
    return True if n == 0 else is_odd(n - 1)

def is_odd(n):
    return False if n == 0 else is_even(n - 1)

print(is_even(10), is_odd(7))         # True True

Recursion shines	Prefer iteration
Trees, graphs (DFS), nested data	Simple counting loops
Divide and conquer (merge sort, quick sort)	Linear chains deeper than ~1000
Backtracking & top-down DP with `@cache`	Hot loops where call overhead matters

What is the default recursion limit in Python and how do you work around it?

Does Python optimise tail recursion?

How do you speed up a recursive solution with overlapping subproblems?