Đệ quy & Chia để trịRecursion & Divide and Conquer

Part of the Data Structures & Algorithms Roadmap knowledge base.

Overview

Recursion is a way of solving a problem by expressing it in terms of a smaller instance of the same problem. A recursive function calls itself on a reduced input, and keeps doing so until the input is small enough to answer outright. That “small enough” case is the base case; the self-referential step is the recursive case. Every correct recursive function has both, and gets closer to the base case on every call — a recursion that does not shrink its input is an infinite loop with worse failure behaviour, because instead of spinning forever it exhausts memory and crashes.

The reason recursion matters is not that it is elegant — it often is, but elegance does not justify a technique. It matters because a large class of data structures are themselves recursively defined, and code that mirrors the shape of the data is the code that is easiest to get right. A binary tree is a node with a left subtree and a right subtree, each of which is a binary tree. A directory contains files and directories. A JSON value is a scalar, or a list of JSON values, or a map of strings to JSON values. Writing a traversal of any of these iteratively means hand-rolling a stack; writing it recursively means writing down the definition and letting the language’s call stack do the bookkeeping.

Divide and conquer is the algorithmic technique built on top of recursion. It has three named steps: divide the problem into independent subproblems of the same kind, conquer them by recursing (until they are small enough to solve directly), and combine the subresults into an answer for the original. Merge sort and binary search are the canonical examples, and the reason divide and conquer produces such good complexities is arithmetic: cutting the input in half each time gives a recursion depth of log n rather than n, and n log n beats n² decisively once n gets past a few thousand.

This note covers the mechanics of recursion (the call stack, depth limits, tail calls), the analysis tools (recursion trees, the Master Theorem), the divide-and-conquer pattern with worked implementations, and memoization — which is the exact point where recursion turns into dynamic programming.

Fundamentals

The two components: base case and recursive case

def factorial(n):
    """n! computed recursively. Precondition: n >= 0."""
    if n <= 1:              # base case — answer known without recursing
        return 1
    return n * factorial(n - 1)   # recursive case — same problem, smaller input

Three things must hold for this to work, and every recursion bug is a violation of one of them:

1. The base case is reachable. factorial(-1) recurses forever because n - 1 moves away from n <= 1. Guarding the precondition, or writing the base case as if n <= 1 rather than if n == 1, is what makes it robust.
2. The recursive call is on a strictly smaller input. “Smaller” needs a well-founded measure — a shorter list, a smaller integer, a subtree rather than the tree. f(n) calling f(n) is not smaller; f(n) calling f(n // 2) is, as long as n // 2 < n, which fails at n = 0 and n = 1 — so those must be base cases.
3. You trust the recursive call. This is the psychological hurdle. When writing factorial(n), do not trace the whole stack in your head. Assume factorial(n - 1) already returns the correct answer for n - 1 (the “recursive leap of faith”) and ask only: given that, is n * factorial(n - 1) correct? This is just induction — base case plus inductive step — and it is the same reasoning as a loop invariant.

The call stack

Recursion is not magic; it is the ordinary function-call mechanism used repeatedly. Each call pushes a stack frame holding that call’s parameters, local variables, and the return address. When the call returns, its frame is popped and control resumes in the caller. Because the frames are pushed and popped in LIFO order, the runtime uses a stack for them — the call stack.

For factorial(4), the stack grows to depth 4, then unwinds:

push factorial(4)   ->  needs 4 * factorial(3)
push factorial(3)   ->  needs 3 * factorial(2)
push factorial(2)   ->  needs 2 * factorial(1)
push factorial(1)   ->  base case, returns 1

           frames on the stack at the deepest point
           +------------------+
   top ->  | factorial(1) n=1 |  returns 1
           | factorial(2) n=2 |  waiting: 2 * ?
           | factorial(3) n=3 |  waiting: 3 * ?
   base -> | factorial(4) n=4 |  waiting: 4 * ?
           +------------------+

unwind: 1 -> 2*1=2 -> 3*2=6 -> 4*6=24

Two consequences follow immediately and are the source of most practical trouble:

• Recursion costs memory proportional to its depth. A recursion d levels deep holds d frames alive at once, so its space complexity is O(d) even if it allocates nothing itself. factorial(n) is O(n) time and O(n) space; the iterative version is O(1) space.
• The work “after the recursive call” happens on the way back up. In n * factorial(n - 1) the multiplication is pending while the deeper calls run. This is what makes the call non-tail and forces the frame to stay alive.

Stack depth limits and sys.setrecursionlimit

CPython caps recursion depth to stop a runaway recursion from overflowing the operating system’s stack and segfaulting. The default is 1000, and hitting it raises RecursionError.

import sys

print(sys.getrecursionlimit())   # 1000 by default

def depth(n):
    return 1 if n == 0 else 1 + depth(n - 1)

# depth(2000)  ->  RecursionError: maximum recursion depth exceeded

sys.setrecursionlimit(20000)     # raise it — but understand what you are raising
print(depth(15000))              # 15001

The limit is a guard, not the actual capacity. The real constraint is the size of the thread’s stack (commonly 8 MB on Linux, 512 KB for non-main threads in some runtimes). Raising setrecursionlimit past what the stack can hold does not raise a clean Python exception — it crashes the interpreter. CPython 3.12+ decoupled pure-Python calls from the C stack, which makes deep pure-Python recursion much safer than it used to be, but recursion that passes back through C (a __repr__, a comparison operator, re matching, a C-implemented iterator) still consumes C stack.

If you need genuinely deep recursion, the honest options are, in order of preference:

1. Rewrite it iteratively with an explicit stack. Always available, always safe.
2. Reduce the depth algorithmically — e.g. in quicksort, recurse into the smaller partition and loop on the larger, which bounds depth at O(log n) regardless of pivot quality.
3. Run it on a thread with a larger stack, only if 1 and 2 are genuinely impossible:

import sys, threading

def run_deep():
    sys.setrecursionlimit(200_000)
    print(depth(150_000))

threading.stack_size(512 * 1024 * 1024)     # 512 MB stack for this thread
t = threading.Thread(target=run_deep)
t.start()
t.join()

This is a competitive-programming trick, not a production pattern. In production, a recursion whose depth is driven by input size is a denial-of-service vector: a deeply nested JSON document crashes a recursive-descent parser. Bound the depth explicitly and reject input that exceeds it.

Direct vs indirect recursion

Direct recursion is a function calling itself. Indirect (or mutual) recursion is a cycle through two or more functions: A calls B, B calls A. It is less common but perfectly ordinary, and it is the natural shape for grammars where two categories are defined in terms of each other.

def is_even(n):
    """Mutual recursion — a deliberately silly parity check that shows the shape."""
    if n == 0:
        return True
    return is_odd(n - 1)

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

The real use is a recursive-descent parser, where the grammar itself is mutually recursive (expr contains term, term contains factor, and factor can be a parenthesised expr):

def parse_expr(tokens, i):
    """expr := term (('+' | '-') term)*"""
    value, i = parse_term(tokens, i)
    while i < len(tokens) and tokens[i] in ("+", "-"):
        op = tokens[i]
        rhs, i = parse_term(tokens, i + 1)
        value = value + rhs if op == "+" else value - rhs
    return value, i

def parse_term(tokens, i):
    """term := factor (('*' | '/') factor)*"""
    value, i = parse_factor(tokens, i)
    while i < len(tokens) and tokens[i] in ("*", "/"):
        op = tokens[i]
        rhs, i = parse_factor(tokens, i + 1)
        value = value * rhs if op == "*" else value / rhs
    return value, i

def parse_factor(tokens, i):
    """factor := NUMBER | '(' expr ')'  -- closes the mutual-recursion cycle"""
    if tokens[i] == "(":
        value, i = parse_expr(tokens, i + 1)
        return value, i + 1          # skip the closing ')'
    return int(tokens[i]), i + 1

tokens = ["2", "+", "3", "*", "(", "4", "-", "1", ")"]
print(parse_expr(tokens, 0)[0])      # 11

The one thing to watch with indirect recursion is that the “input gets smaller” argument now has to hold around the whole cycle, not per function. A left-recursive grammar rule (expr := expr '+' term) makes parse_expr call itself with the index unchanged — infinite recursion, and the classic reason recursive-descent parsers require the grammar to be rewritten without left recursion.

Converting recursion to iteration

Every recursion can be made iterative, because the call stack is just a stack you can manage yourself. There are two levels of conversion.

Level 1 — the recursion is linear and the pending work is trivial. Then a plain loop with an accumulator suffices:

def factorial_iter(n):
    """O(n) time, O(1) space — no stack frames at all."""
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

Level 2 — the recursion branches. Then you need an explicit stack, and you have to encode “where was I in this frame” as state. Compare the recursive and iterative in-order tree traversals:

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

def inorder_recursive(node, out):
    if node is None:                 # base case
        return
    inorder_recursive(node.left, out)
    out.append(node.value)
    inorder_recursive(node.right, out)

def inorder_iterative(root):
    """Same traversal, explicit stack. The `stack` here IS the call stack."""
    out, stack, node = [], [], root
    while stack or node is not None:
        while node is not None:      # descend left, remembering the path
            stack.append(node)
            node = node.left
        node = stack.pop()           # backtrack to the deepest unvisited node
        out.append(node.value)
        node = node.right            # then go right
    return out

The iterative version is longer and harder to read, which is exactly the trade: you buy freedom from the depth limit and a small constant-factor speedup, and you pay in clarity. Convert when you must (depth is unbounded, or profiling shows call overhead matters), not on principle.

Tail recursion, and why Python does not optimize it

A call is tail recursive when the recursive call is the last thing the function does — nothing is pending after it returns. return n * factorial(n - 1) is not tail recursive (the multiply is pending). This version is:

def factorial_tail(n, acc=1):
    if n <= 1:
        return acc
    return factorial_tail(n - 1, acc * n)   # nothing pending — pure tail call

Because nothing is pending, the caller’s frame is dead the moment the tail call is made. A compiler can therefore reuse the frame instead of pushing a new one, turning the recursion into a loop with O(1) stack. This is tail call optimization (TCO), and Scheme mandates it, while Lua, Scala (for self-calls via @tailrec), and most functional languages provide it. LLVM will do it for C/C++ at -O2 when the shape permits.

CPython does not do TCO, deliberately. Guido van Rossum’s stated reasons are worth knowing because they are engineering judgements, not oversights:

• It destroys stack traces. The eliminated frames are exactly the ones you want in a traceback when something goes wrong deep in a recursion. Python treats debuggability as more valuable than the optimization.
• It makes the optimization invisible and fragile. Whether TCO applies depends on subtle syntactic properties; a refactor that adds a try/finally or a with silently reintroduces O(n) stack and turns working code into a RecursionError in production.
• Python is not a functional language. Loops are the idiomatic construct. Making recursion competitive with loops would encourage a style that reads poorly in Python.

The practical consequence: in Python, if you find yourself writing a tail-recursive function, write the loop instead. The transformation is mechanical — the accumulator becomes a variable, the parameters become loop variables:

def factorial_loop(n):
    """Mechanical de-recursion of factorial_tail. O(1) stack."""
    acc = 1
    while n > 1:
        n, acc = n - 1, acc * n     # exactly the arguments of the tail call
    return acc

Key Concepts

The recursion tree as an analysis tool

To analyse a recursive algorithm, draw the tree of calls: each node is a call, its children are the calls it makes, and the node is labelled with the work done at that node excluding its children. Total cost is the sum over all nodes — which is easiest to compute level by level.

For merge sort, T(n) = 2T(n/2) + Θ(n):

level 0:                  n                     work = n
                        /   \
level 1:            n/2      n/2                work = 2·(n/2) = n
                   /   \    /   \
level 2:        n/4   n/4  n/4   n/4            work = 4·(n/4) = n
                 ...          ...
level log n:   1  1  1  1  ...  1  1  1         work = n·1     = n
                                                ------------------
                                          total = n per level × (log n + 1) levels
                                                = Θ(n log n)

Every level costs n, and there are log₂ n + 1 levels because the input halves each time — hence Θ(n log n).

Now the same tool on naive Fibonacci, T(n) = T(n−1) + T(n−2) + Θ(1):

                        fib(5)
                   /            \
              fib(4)            fib(3)
             /      \          /      \
        fib(3)    fib(2)   fib(2)   fib(1)
        /    \     /   \    /   \
   fib(2) fib(1) f(1) f(0) f(1) f(0)
    /   \
 f(1)  f(0)

The tree is nearly a full binary tree of depth n, so the node count — and therefore the runtime — is exponential: Θ(φⁿ) where φ ≈ 1.618. But look at the repetition: fib(3) is computed twice, fib(2) three times, fib(1) five times. That redundancy is overlapping subproblems, and it is precisely what memoization removes.

The recursion tree also handles unbalanced splits that the Master Theorem cannot. For T(n) = T(n/3) + T(2n/3) + n, every level still costs at most n, the shallowest leaf is at depth log₃ n and the deepest at log_{3/2} n, so T(n) = Θ(n log n) — the same as a balanced split, just with a bigger constant. This is the formal reason quicksort survives a consistently 1:9 split.

Divide and conquer: divide, conquer, combine

                +---------------------------+
                |    problem of size n      |
                +---------------------------+
                             |  DIVIDE into a subproblems of size n/b
              +--------------+--------------+
              v                             v
       +-------------+              +-------------+
       | size n/b    |     ...      | size n/b    |   CONQUER: recurse
       +-------------+              +-------------+   (base case if small)
              |                             |
              +--------------+--------------+
                             v  COMBINE the subresults
                +---------------------------+
                |         answer            |
                +---------------------------+

The technique pays off when the combine step is cheaper than solving the problem directly. Merge sort works because merging two sorted halves is O(n) while sorting from scratch is O(n log n). Divide and conquer fails to help when the subproblems overlap (then you want DP) or when combining is as expensive as the original problem.

Merge sort — the canonical example

def merge_sort(arr):
    """Divide: split in half. Conquer: sort each half. Combine: merge."""
    if len(arr) <= 1:                      # base case: 0 or 1 element is sorted
        return arr[:]
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])           # conquer
    right = merge_sort(arr[mid:])
    return merge(left, right)              # combine — the O(n) step

def merge(left, right):
    """Merge two sorted lists into one sorted list. O(len(left) + len(right))."""
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:            # <= keeps the sort stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])                   # one side is exhausted; append the rest
    out.extend(right[j:])
    return out

print(merge_sort([5, 2, 9, 1, 5, 6]))      # [1, 2, 5, 5, 6, 9]

Θ(n log n) in all cases — the recursion depth does not depend on the data, only on n. Space is Θ(n) for the merge buffers plus Θ(log n) of stack. See ./08-sorting-algorithms.md for the full comparison against quicksort and heapsort.

Binary search — divide and conquer with an empty combine step

def binary_search_rec(arr, target, lo=0, hi=None):
    """Divide: pick the midpoint. Conquer: recurse into ONE half. Combine: nothing."""
    if hi is None:
        hi = len(arr) - 1
    if lo > hi:                            # base case: empty range
        return -1
    mid = lo + (hi - lo) // 2              # avoids overflow in fixed-width languages
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, hi)
    return binary_search_rec(arr, target, lo, mid - 1)

This is the degenerate case: it divides into two subproblems but only conquers one, and there is nothing to combine. T(n) = T(n/2) + Θ(1) = Θ(log n). It is also naturally tail recursive, so the iterative version in ./09-search-algorithms.md is the one to actually use in Python.

Counting inversions — divide and conquer that is not a sort

An inversion is a pair i < j with arr[i] > arr[j]; the count measures how far from sorted a list is. Brute force is Θ(n²). Piggy-backing on merge sort makes it Θ(n log n), and the insight is the whole reason divide and conquer is worth learning: when the left half’s element is bigger, every remaining element in the left half is also bigger than right[j], so one comparison counts many inversions at once.

def count_inversions(arr):
    """Returns (sorted_copy, inversion_count). Theta(n log n)."""
    if len(arr) <= 1:
        return arr[:], 0
    mid = len(arr) // 2
    left, a = count_inversions(arr[:mid])
    right, b = count_inversions(arr[mid:])
    merged, cross = _merge_count(left, right)
    return merged, a + b + cross           # combine: left + right + cross-boundary

def _merge_count(left, right):
    out, i, j, inversions = [], 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            # left[i..] are all > right[j], so this contributes len(left) - i pairs
            inversions += len(left) - i
            out.append(right[j]); j += 1
    out.extend(left[i:]); out.extend(right[j:])
    return out, inversions

print(count_inversions([2, 4, 1, 3, 5])[1])   # 3  -> (2,1), (4,1), (4,3)

Karatsuba multiplication — beating the obvious bound

Multiplying two n-digit numbers the schoolbook way is Θ(n²). Splitting each number in half gives x = x₁·10^m + x₀, and the naive expansion needs four half-size products — T(n) = 4T(n/2) + Θ(n), which is still Θ(n²), so nothing is gained. Karatsuba’s trick is an algebraic identity that computes the middle term from the other two, needing only three products:

def karatsuba(x, y):
    """Theta(n^1.585) integer multiplication. Three half-size products, not four."""
    if x < 10 or y < 10:                   # base case: single-digit multiply
        return x * y
    n = max(x.bit_length(), y.bit_length())
    m = (n // 2)
    high_x, low_x = divmod(x, 1 << m)
    high_y, low_y = divmod(y, 1 << m)

    z0 = karatsuba(low_x, low_y)                       # product 1
    z2 = karatsuba(high_x, high_y)                     # product 2
    z1 = karatsuba(low_x + high_x, low_y + high_y) - z0 - z2   # product 3

    return (z2 << (2 * m)) + (z1 << m) + z0

print(karatsuba(123456789, 987654321) == 123456789 * 987654321)   # True

T(n) = 3T(n/2) + Θ(n) = Θ(n^log₂3) = Θ(n^1.585). Dropping one of four recursive calls changed the exponent — that is the leverage divide and conquer gives you, and the same trick shape drives Strassen’s matrix multiplication (8T(n/2) → 7T(n/2), giving Θ(n^2.807) instead of Θ(n³)).

The Master Theorem

Most divide-and-conquer recurrences have the form

T(n) = a·T(n/b) + f(n)          a >= 1,  b > 1

where a is the number of subproblems, n/b is their size, and f(n) is the cost of dividing plus combining. The Master Theorem answers all of them by comparing f(n) against the watershed function n^(log_b a) — which is the total cost of the leaves.

Case 3’s second condition is the regularity condition; it rules out pathological f that oscillate. In practice, if f is a polynomial times a polylog, regularity holds.

Worked examples:

Two failure modes worth recognising, because they show up in interviews:

• T(n) = 2T(n/2) + n/log n. Here n^(log_b a) = n and f(n) = n/log n is smaller — but not polynomially smaller: there is no ε > 0 with n/log n = O(n^(1−ε)). The theorem has a gap here and simply does not apply. (The true answer, by recursion tree, is Θ(n log log n).)
• Unequal splits. T(n) = T(n/3) + T(2n/3) + n is not of the Master form at all. Use a recursion tree, or the Akra–Bazzi method, which generalises the Master Theorem to T(n) = Σ aᵢT(n/bᵢ) + f(n).

Verify a Master Theorem result empirically before trusting a fiddly case — counting the actual recursive calls takes ten lines:

def merge_sort_counted(arr, counter):
    counter[0] += len(arr)                 # work done at this node (the merge)
    if len(arr) <= 1:
        return arr[:]
    mid = len(arr) // 2
    return merge(merge_sort_counted(arr[:mid], counter),
                 merge_sort_counted(arr[mid:], counter))

import math
for n in (1024, 2048, 4096, 8192):
    c = [0]
    merge_sort_counted(list(range(n, 0, -1)), c)
    print(n, c[0], round(c[0] / (n * math.log2(n)), 3))
# ratio stays ~1.1 as n doubles -> the n log n prediction holds

Memoization — the bridge to dynamic programming

Naive Fibonacci is exponential purely because it recomputes the same subproblems. Memoization is the fix: cache the result of each distinct call and return the cached value on a repeat. Nothing about the algorithm’s shape changes — only the redundant work disappears.

def fib_naive(n):
    """Theta(phi^n) ~ Theta(1.618^n). fib_naive(35) already takes seconds."""
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

def fib_memo(n, cache=None):
    """Theta(n) time, Theta(n) space. Same recursion, memoized."""
    if cache is None:
        cache = {}
    if n < 2:
        return n
    if n in cache:                         # already solved this subproblem
        return cache[n]
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

Why the complexity collapses: there are only n + 1 distinct subproblems (fib(0) … fib(n)), each is computed exactly once, and each costs O(1) beyond its recursive calls. Number of distinct states × cost per state is the standard way to analyse a memoized recursion, and it is the same formula you use for DP.

In production, use the standard library rather than a hand-rolled dict — but know what it costs:

from functools import lru_cache, cache

@cache                          # Python 3.9+; unbounded, equivalent to lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

@lru_cache(maxsize=1024)        # bounded — evicts least-recently-used entries
def expensive(x, y):
    ...

@cache never evicts, so on a long-running service with unbounded argument variety it is a memory leak; @lru_cache(maxsize=N) bounds it. Both require arguments to be hashable, which rules out list and dict parameters — pass tuples, or a key derived from them. And note that the decorated function still recurses: fib(5000) with @cache blows the recursion limit even though the algorithm is linear, because the first call chain descends n frames deep.

Memoization is top-down dynamic programming. The alternative is bottom-up: order the subproblems so that dependencies are computed first, then fill a table with a loop — no recursion, no stack, and often less memory because you can discard old rows.

def fib_bottom_up(n):
    """Theta(n) time, Theta(1) space. No recursion at all."""
    if n < 2:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr     # only the last two values are ever needed
    return curr

The two conditions that make memoization work — overlapping subproblems (the same call recurs) and optimal substructure (the answer is built from subanswers) — are exactly the two conditions for dynamic programming. Divide and conquer, by contrast, has optimal substructure without overlap: merge sort never sorts the same subarray twice, which is why memoizing it would only waste memory. That distinction is the cleanest way to decide which technique a problem wants, and it is developed fully in ./22-dynamic-programming.md.

Where recursion shows up elsewhere in this roadmap

• Tree traversals — in-order, pre-order, post-order are three lines each recursively.
• DFS on graphs — the recursive formulation is the readable one; the iterative one exists for depth safety.
• Quicksort and merge sort — both are divide and conquer, differing in whether the work is in the divide step (quicksort’s partition) or the combine step (merge sort’s merge).
• Backtracking — recursion plus undoing the choice on the way back up.
• Segment trees — build, query, and update are all T(n) = 2T(n/2) + O(1) recursions.
• Database query planners recursively decompose joins the same way; see ../../postgresql-dba/en/10-query-planning-and-performance-tuning.md.

Best Practices

• Write the base case first. It is the part that terminates the recursion and the part most often wrong. Prefer if n <= 1 over if n == 1 so that unexpected inputs terminate rather than recurse forever.
• Make “smaller” a measurable quantity. Before writing the recursive call, name the value that decreases and check it strictly decreases on every path. If you cannot name it, the recursion is not well-founded.
• Take the recursive leap of faith. Assume the recursive call is correct for smaller inputs and verify only the current step. Tracing three levels of the stack by hand is how people convince themselves that correct recursion is wrong.
• Do not use recursion when the depth is driven by untrusted input size. A recursive JSON or XML parser is a crash waiting to happen. Bound the depth explicitly and reject over-deep input with an error, or use an iterative parser.
• Do not write tail recursion in Python. Convert it to a loop — the transformation is mechanical, CPython will never optimize it, and the loop is both faster and immune to RecursionError.
• Reach for sys.setrecursionlimit last, not first. It is a competitive-programming escape hatch. In application code, treat needing it as a signal to restructure the algorithm.
• In quicksort-style recursions, recurse on the smaller side and iterate on the larger. This bounds stack depth at O(log n) even when the partitions are badly unbalanced.
• Add a cutoff to small subproblems. Real merge sort and quicksort implementations switch to insertion sort below ~16 elements, because at that size the recursion overhead exceeds the asymptotic benefit. This is why Python’s Timsort has a “minrun” and why introsort exists.
• Memoize before you optimize anything else. If a recursion is slow, check for repeated subproblems first — a one-line @cache frequently converts exponential to linear, and no amount of micro-optimization will.
• Use @lru_cache(maxsize=N), not @cache, on long-lived services. An unbounded cache keyed on user input is an unbounded memory leak.
• Draw the recursion tree before reaching for the Master Theorem. The tree always works, tells you where the cost is, and does not have gaps between its cases. The Master Theorem is a shortcut for the common shapes, not a substitute for understanding.
• Check the Master Theorem’s preconditions. “Smaller” in Case 1 and “larger” in Case 3 mean polynomially smaller/larger. n/log n versus n fails that test, and applying the theorem anyway gives the wrong answer.
• Prefer divide and conquer when subproblems are independent, dynamic programming when they overlap. Memoizing merge sort is pure waste; not memoizing Fibonacci is exponential waste. The presence or absence of overlap decides which you have.

References

• roadmap.sh — Data Structures & Algorithms
• Recursion (computer science) — Wikipedia
• Divide-and-conquer algorithm — Wikipedia
• Master theorem (analysis of algorithms) — Wikipedia
• Akra–Bazzi method — Wikipedia
• Tail call — Wikipedia
• Karatsuba algorithm — Wikipedia
• Memoization — Wikipedia
• CLRS — Introduction to Algorithms, Chapter 4: Divide-and-Conquer
• MIT 6.006 — Introduction to Algorithms (OpenCourseWare)
• Python Documentation — sys.setrecursionlimit
• Python Documentation — functools.lru_cache and functools.cache
• cp-algorithms — Divide and Conquer DP
• Big-O Cheat Sheet