Recursion and Divide and Conquer

Recursion solves a problem by solving smaller instances of the same problem. Divide and conquer is the most common way to use it: split the input into independent parts, solve each part recursively, and combine the answers. Almost every tree question, merge sort, quickselect and backtracking are built on these two ideas.

Intuition

A recursive function needs exactly two things:

1. A base case that answers the smallest inputs directly (an empty tree, an array of length 0 or 1, n == 0).
2. A recursive step that reduces the input and calls the function on something strictly smaller.

The key mental move is to define a contract and trust it. Write one sentence for what the function returns, for example "height(node) returns the number of nodes on the longest downward path from node". When you write the body, assume the recursive calls already honor that contract and only decide how to combine their results. Do not mentally unroll the calls; that is where people get lost.

Divide and conquer adds structure to the recursive step:

• Divide the problem into smaller subproblems of the same kind.
• Conquer each subproblem recursively.
• Combine the sub-answers into the answer for the whole input.

The combine step runs after the children return, exactly like a post-order tree traversal. If the subproblems overlap (the same subproblem is solved many times), plain divide and conquer wastes work: add memoization, which turns it into dynamic programming.

When to use it in interviews / OAs

• Trees: nearly every binary tree question is "compute something for the left subtree, something for the right subtree, combine".
• The input splits naturally into halves or around a pivot: sorting, k-th element, counting inversions, building a balanced BST from a sorted array.
• The answer for a string or expression depends on a split point: every operator in an expression, every cut position in a string.
• A quantity can be computed from half-size versions of itself: fast exponentiation, multiplying large numbers.
• Self-similar structure: nested lists, fractals, Tower of Hanoi, generating all valid combinations.

Template

The node class used below:

from dataclasses import dataclass
from typing import Optional


@dataclass
class TreeNode:
    val: int
    left: Optional["TreeNode"] = None
    right: Optional["TreeNode"] = None

Recursion by contract: counting downward paths with a given sum

Count the downward paths (parent to child, starting and ending anywhere) whose values add up to target. Two contracts make the first solution almost write itself:

• from_node(node, remaining): the number of valid paths that start at node.
• path_sum_naive(root, target): the number of valid paths anywhere in the tree rooted at root.

def path_sum_naive(root: Optional[TreeNode], target: int) -> int:
    def from_node(node: Optional[TreeNode], remaining: int) -> int:
        if node is None:
            return 0
        here = 1 if node.val == remaining else 0
        rest = remaining - node.val
        return here + from_node(node.left, rest) + from_node(node.right, rest)

    if root is None:
        return 0
    return (from_node(root, target)
            + path_sum_naive(root.left, target)
            + path_sum_naive(root.right, target))

This is O(n^2) on a skewed tree because every node restarts a walk below it. The O(n) version keeps prefix sums of the current root-to-node path in a hash map: a path ending at the current node sums to target exactly when some earlier prefix equals prefix - target. Undo the count when leaving a node so siblings never see each other's prefixes:

from collections import defaultdict


def path_sum(root: Optional[TreeNode], target: int) -> int:
    counts: defaultdict[int, int] = defaultdict(int)
    counts[0] = 1  # the empty prefix above the root

    def dfs(node: Optional[TreeNode], prefix: int) -> int:
        if node is None:
            return 0
        prefix += node.val
        found = counts[prefix - target]  # paths that end at this node
        counts[prefix] += 1
        found += dfs(node.left, prefix) + dfs(node.right, prefix)
        counts[prefix] -= 1  # leaving this node: remove its prefix
        return found

    return dfs(root, 0)

Divide and conquer: halve the problem

x^n equals (x^(n/2))^2, times one more x when n is odd. Solving the half-size problem once and reusing it gives T(n) = T(n/2) + O(1) = O(log n):

def my_pow(x: float, n: int) -> float:
    if n < 0:
        return 1 / my_pow(x, -n)
    if n == 0:
        return 1.0
    half = my_pow(x, n // 2)  # compute once, use twice
    return half * half * (x if n % 2 else 1)

Calling my_pow(x, n // 2) twice instead of storing it would make the recursion O(n) again.

Divide at every split point, memoize overlapping subproblems

Return every value an arithmetic expression can take under different parenthesizations. Any operator can be the last one evaluated, so split there, solve both sides recursively and combine every pair of results. The same substrings appear in many splits, so cache them:

from functools import cache


def diff_ways(expr: str) -> list[int]:
    @cache
    def solve(s: str) -> tuple[int, ...]:
        results = []
        for i, ch in enumerate(s):
            if ch in "+-*":
                for a in solve(s[:i]):
                    for b in solve(s[i + 1:]):
                        results.append(a + b if ch == "+" else a - b if ch == "-" else a * b)
        return tuple(results) if results else (int(s),)  # no operator: a plain number

    return list(solve(expr))

When recursion is too deep: use an explicit stack

Python's default recursion limit is about 1000 frames, so a skewed tree or a long linked list with 10^5 nodes crashes a recursive solution. Any recursion can be rewritten with your own stack that stores what each frame would have held:

def max_depth_iterative(root: Optional[TreeNode]) -> int:
    best = 0
    stack = [(root, 1)] if root else []
    while stack:
        node, depth = stack.pop()
        best = max(best, depth)
        for child in (node.left, node.right):
            if child:
                stack.append((child, depth + 1))
    return best

Complexity

• Time: write the recurrence and solve it (see the complexity article). Two half-size calls plus linear combining is O(n log n); one half-size call plus constant work is O(log n); visiting each tree node once is O(n).
• Space: the recursion depth times the frame size, plus any memo table. A balanced tree uses O(log n) stack, a skewed tree O(n).
• path_sum_naive is O(n^2) in the worst case, path_sum is O(n), my_pow is O(log n), and max_depth_iterative is O(n) time with O(n) stack in the worst case.

Common pitfalls

• Missing or wrong base case, or a recursive call that does not shrink the input, causing infinite recursion.
• Exponential recomputation. If the same arguments recur, memoize with functools.cache (arguments must be hashable).
• Slicing in every call. solve(nums[1:]) copies the list each time and turns O(n) recursion into O(n^2); pass indices instead.
• Forgetting to undo shared state. If you mutate a shared list, set or counter before recursing, revert it after the call returns.
• Recursion depth. For inputs with 10^4 or more levels, use an explicit stack. Raising the limit with sys.setrecursionlimit can still crash the interpreter on its native stack.
• Mixing "return a value" and "update a global" in the same function. Pick one style; returning values composes better.

Interview variations

• Tree DP: return several values from each child (for example "best path through me" and "best path ending at me") to solve diameter or maximum path sum in one pass.
• Rebuild a tree from preorder and inorder traversals: the first preorder value is the root and splits the inorder array.
• Merge sort family: count inversions, count smaller elements to the right, sort a linked list.
• Quickselect: partition once and recurse into one side only, O(n) on average.
• Maximum subarray by divide and conquer: the best subarray lies in the left half, the right half, or crosses the middle; O(n log n), a good warm-up before Kadane's O(n) algorithm.
• Split-point recursion with memoization: expression parenthesization, word break, burst-balloons-style interval problems (which become interval DP).