Recursion and Divide-and-Conquer

TL;DR: A recursive function is two parts: a base case that returns without recursing, and a recursive step that reduces the problem and calls itself. Divide-and-conquer is recursion where you split the input into independent pieces, solve each, and merge (merge sort, quickselect). The same decomposition, once subproblems start overlapping, becomes dynamic programming the moment you add memoization.

Two parts, and the stack that holds them

Every correct recursion needs a base case (the smallest input you can answer directly) and a recursive step (do a little work, then call yourself on something strictly smaller). Miss the base case, or fail to shrink the input, and you recurse forever until the stack overflows.

The call stack is the part candidates underestimate. Each pending call holds a frame: its local variables and where to resume. A recursion n deep uses O(n) stack space even if it does O(1) work per frame. That is why a recursive sum over a million-element list crashes in Python (default limit ~1000) while the loop version is fine. Depth is a real cost, not a free abstraction.

def merge_sort(a):
    if len(a) <= 1:            # base case: already sorted
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])   # independent subproblem
    right = merge_sort(a[mid:])  # independent subproblem
    return merge(left, right)    # combine

def merge(x, y):
    out, i, j = [], 0, 0
    while i < len(x) and j < len(y):
        if x[i] <= y[j]:
            out.append(x[i]); i += 1
        else:
            out.append(y[j]); j += 1
    out.extend(x[i:]); out.extend(y[j:])
    return out

Divide-and-conquer: independent subproblems

The defining property is independence: the left half of merge sort knows nothing about the right half. That is what lets you reason about each piece alone and what makes the work parallelizable. Merge sort splits in half, sorts each, merges in O(n): the recurrence T(n) = 2T(n/2) + O(n) gives O(n log n).

Quickselect is the asymmetric cousin. To find the k-th smallest, partition around a pivot, then recurse into only the side that contains k, discarding the other half. Because you throw away work each step, the recurrence is T(n) = T(n/2) + O(n) on average, which sums to O(n), beating a full O(n log n) sort when you only need one order statistic. Worst case is O(n^2) with adversarial pivots; randomizing the pivot makes that astronomically unlikely.

The bridge to iteration and DP

Two transformations come up constantly.

Recursion to iteration. Any recursion can be made iterative with an explicit stack, and a tail-recursive call (the recursive call is the last thing the function does) becomes a plain loop with no stack growth. Python does not optimize tail calls, so converting deep recursions to loops is a real fix for stack-overflow bugs.

Recursion to DP. When subproblems start to overlap (naive recursive Fibonacci recomputes fib(3) exponentially many times), recursion alone is wasteful. Add a cache keyed on the arguments (memoization) and each subproblem is solved once: exponential collapses to linear. Memoized recursion is top-down dynamic programming. Flip it to fill a table bottom-up and you have the iterative DP form. The decision tree: independent subproblems means divide-and-conquer; overlapping subproblems means memoize, which is DP.

Why interviewers probe this

Recursion is the cheapest test of whether you can decompose a problem. The screen: can you state the base case and recursive step out loud before writing code, and can you say what the call stack costs? The strong-answer move is to name the recurrence (T(n) = 2T(n/2) + O(n) is O(n log n)) and to flag stack depth as a real constraint, not hand-wave it. The follow-up they hold in reserve: "this recurses 10^6 deep, what breaks and how do you fix it?" The answer is stack overflow, convert to an explicit stack or iteration. A second common follow-up: "you are recomputing the same subproblem, what now?" That is the memoization door into DP.

Common misconceptions

• "Recursion is just a slower loop." For independent splits and tree traversal it is often the clearest and asymptotically best form; the cost is stack space, not necessarily time.
• "Recursion has no memory cost." Each pending call holds a frame; depth-n recursion is O(n) space even with O(1) work per call.
• "Divide-and-conquer always sorts everything." Quickselect and binary search recurse into one side only and beat a full sort when you need a single element or position.
• "Memoization changes the answer." It only caches results of pure subproblems; same output, exponential-to-polynomial speedup. That is the recursion-to-DP bridge.

Key takeaways

• A recursion is a base case plus a recursive step that shrinks the input; forgetting either causes infinite recursion or wrong results.
• Divide-and-conquer requires independent subproblems; merge sort recurses into both halves (O(n log n)), quickselect into one (O(n) average).
• The call stack costs O(depth) space; deep recursions overflow and should be converted to iteration or an explicit stack.
• Overlapping subproblems plus a cache equals memoization, which is top-down dynamic programming.