Recursion & divide-and-conquer

Try it: see Fibonacci recurse

Two modes, same problem: compute fib(n). Naive recursion explodes into an exponential tree where the same subproblems are recomputed dozens of times. Memoised recursion adds a cache; the second time fib(3) is asked, the cache returns instantly.

This is the bridge from recursion to dynamic programming. The DP pattern is just memoised recursion plus, sometimes, a bottom-up rewrite. If you internalise that bridge, half of "DP problems" become recursion problems with a cache decorator.

1 · Why recursion is the mental model for trees and divide-and-conquer

Recursion isn't a control-flow gimmick. It's the algorithmic mirror of mathematical induction: prove the base case, prove that the step from k to k+1 holds, and you've proven it for all n. Code the base case, code the step, and you've solved the problem for all n. Every recursive function defines an implicit tree of calls. Every divide-and-conquer algorithm is a literal tree where leaves are subproblems small enough to solve directly and internal nodes are combine operations.

Almost every problem on a tree, a graph, a nested data structure, or a hierarchical decomposition is recursion in its natural form. Iterative versions exist (an explicit stack replaces the call stack), but they obscure the structure. The recursive form lets you read the algorithm the way you'd describe it on a whiteboard: "if the input is small, do this; otherwise, split and combine." That one-to-one correspondence between thinking and coding is why recursion is the default reach for an entire family of problems. It's also why senior engineers reach for it even when iteration would work.

• Trees. Every operation on a tree is recursive by nature. The structure is recursive (a tree is a root and zero or more subtrees, each of which is a tree), so the algorithms inherit the recursion. Traversal, depth, diameter, LCA, serialisation: all five lines once you write the contract.
• Divide-and-conquer. Sort, search, multiply, compute convex hulls: the recurrence T(n) = a·T(n/b) + f(n) is the signature pattern. Merge sort splits in half and combines linearly. Karatsuba multiplies n-digit numbers in O(n^log₂3) via three sub-multiplications of half-size. Strassen multiplies n×n matrices in O(n^log₂7). All are recursion + a clever combine.
• Recursive data structures. JSON, XML, S-expressions, abstract syntax trees, file systems, comment threads, organisation charts: anything with arbitrary nesting depth is parsed and traversed recursively. Iteration on these requires either a hand-managed stack or generators, both of which are recursion in disguise.
• Enumeration and backtracking. All subsets, all permutations, all parenthesisations, all valid Sudoku boards: these are recursive because each choice opens a fresh subproblem (the remaining choices). Backtracking is just recursion + an undo step.

2 · Intuition: the leap of faith

The single most important trick in recursive design is trusting that the recursive call works. Don't trace it in your head. Don't simulate the call stack. Specify the contract: what the function takes in, what it returns, what it promises about side effects. Then code to that contract, and assume every recursive call to that function honours the contract perfectly. This is the "leap of faith", and it's what separates candidates who write clean recursion in three lines from candidates who write spaghetti and spend twenty minutes debugging.

The reason this works: induction. If the base case is right, and the step assuming the contract holds for smaller inputs is right, then by induction the contract holds for all inputs. You're not actually trusting an unverified call — you're trusting the inductive structure. The call will work because you've coded the step to work, and the step's correctness reduces to the recursive call's correctness, which reduces to a smaller call, which eventually reduces to the base case, which you've manually verified.

• Step 1: write the contract in one sentence. "maxDepth(node) returns the depth of the subtree rooted at node, or 0 if node is nil." That sentence is the function's promise. Print it as a comment at the top of the function.
• Step 2: handle the base case. The smallest input that satisfies the contract trivially. For trees, usually nil or a leaf. Write the base case first, before the recursion.
• Step 3: write the recursive step assuming the contract holds for the children. Don't ask "but how does maxDepth(left) work?". Trust it. Just compose: return 1 + max(maxDepth(left), maxDepth(right)).
• Step 4: verify the base + step on a tiny input. A two-node tree, a three-node tree. If the base + step are right, induction gives you the rest for free. Don't trace 100-node trees in your head.

A small Fibonacci recursion tree (and what memoisation prunes)

3 · How to recognise it

Recursion is the right pattern when the problem has a self-similar structure: when solving a smaller instance of the same problem helps solve the larger one. Beyond the obvious "input is a tree" tell, six recognisable shapes recur:

• The input is a tree. Always recursion (or BFS / iterative DFS, but recursion is the default reach).
• The input has a "subproblem on the left, subproblem on the right" shape. Merge sort, quickselect, binary search trees.
• "Find all" enumerations. All permutations, all subsets, all paths. Backtracking is recursion in disguise.
• The natural problem statement is recursive. "The Fibonacci sequence is defined as F(n) = F(n-1) + F(n-2)": code mirrors definition.
• You can describe the answer as "answer to a smaller version + a constant-time combine". The classic divide-and-conquer recipe.

Shape A: tree / graph traversal

• Tell. Input is a tree node, a graph adjacency list, or a nested data structure. You need to visit every node and compute / aggregate per node.
• The contract. visit(node) returns aggregateOver(node and its descendants). Base case: nil or leaf. Recursive step: combine results from children.
• Canonical: LC 104 Max Depth, LC 226 Invert Tree, LC 102 Level Order (BFS variant), LC 200 Number of Islands (graph DFS).

Shape B: divide-and-conquer

• Tell. Split input into two (or more) halves, solve each recursively, combine. The recurrence is T(n) = a·T(n/b) + f(n); see section 16 (Master Theorem) for the complexity analysis.
• The contract. solve(range) returns answer for that range. Base case: size 1 (already solved). Recursive step: split, recurse, merge.
• Canonical: merge sort, quick sort, quickselect (LC 215), binary search variants, LC 23 Merge K Sorted Lists, LC 53 Maximum Subarray (divide-and-conquer version).

Shape C: generation / enumeration

• Tell. "Generate all X", "list all Y", "count valid Z". The output size is exponential in the input: 2^n subsets, n! permutations, Catalan(n) parenthesisations.
• The contract. generate(prefix, remaining) emits all completions of prefix using elements of remaining. Base case: remaining empty → emit prefix. Recursive step: try each next choice, recurse.
• Canonical: LC 78 Subsets, LC 46 Permutations, LC 22 Generate Parentheses, LC 39 Combination Sum, LC 51 N-Queens.

Shape D: recursive data structures (trees, linked lists, nested arrays)

• Tell. The data itself is defined recursively. A linked list is a node + a (smaller) linked list. A nested array is an array of values or nested arrays. An S-expression is a token or a list of S-expressions.
• The contract. Match the structure: handle base (empty/atom) and recursive (node + rest, head + tail) separately. The shape of the function matches the shape of the data.
• Canonical: LC 206 Reverse Linked List, LC 339 Nested List Weight Sum, LC 341 Flatten Nested List Iterator, LC 394 Decode String.

Shape E: decision tree exploration with state

• Tell. At each step you have multiple choices, each leading to a subproblem. You're either searching for any valid completion (backtracking with early return) or aggregating over all completions (count, min, max).
• The contract. explore(state) returns answer for state. Base case: terminal state. Recursive step: for each choice, mutate state, recurse, undo (or pass immutably).
• Canonical: LC 79 Word Search, LC 37 Sudoku Solver, LC 51 N-Queens, LC 980 Unique Paths III.

Shape F: recurrence relations / Master Theorem hints

• Tell. The problem statement gives a recurrence directly: "T(n) = T(n/2) + O(n)" or "f(n) = f(n-1) + g(n)". The code mirrors the math one-to-one.
• The contract. Whatever the recurrence says f(n) means: write that function. Memoise if the recurrence has overlapping subproblems (Fibonacci); don't bother if not (binary search).
• Canonical: LC 70 Climbing Stairs, LC 509 Fibonacci, LC 1137 N-th Tribonacci, LC 894 All Possible Full Binary Trees.

4 · The recursion template

Every recursive function has the same skeleton. Internalise the skeleton; specialising it to a problem becomes mechanical.

// The four-step recursion skeleton — Go form
func solve(input InputT) ResultT {
    // 1. BASE CASE — when do we stop?
    if isBaseCase(input) {
        return baseAnswer(input)
    }

    // 2. DECOMPOSE — split into smaller subproblems
    subInputs := decompose(input)

    // 3. RECURSE — trust each call to return the right answer
    subAnswers := make([]ResultT, len(subInputs))
    for i, si := range subInputs {
        subAnswers[i] = solve(si)
    }

    // 4. COMBINE — assemble sub-answers into this level's answer
    return combine(subAnswers, input)
}

Every recursive solution is a specialisation of these four steps. Identify the base case first, then the recurrence (steps 2–4). If you can't write the base case in one line, the contract is wrong; re-state it.

5 · Canonical example: Maximum depth of binary tree (LC 104)

Problem. Given a binary tree, return its maximum depth (longest root-to-leaf path measured in nodes).

The contract

"Given a node, return the depth of the subtree rooted at it." The base case: an empty subtree has depth 0. The recurrence: max depth = 1 + max(left depth, right depth).

Build the intuition: write the contract first

• What does the function promise? "Given a tree node, return the max depth of the subtree rooted at it." That sentence is the contract.
• What's the base case? The smallest tree: empty. What's the depth of an empty tree?
• What's the recurrence? A non-empty tree's depth is one (for the root) plus the depth of the deeper child. Why "deeper"?
• Why "trust the recursion"? Don't trace the call stack. Assume maxDepth(left) returns the correct depth of the left subtree. Code only the layer that combines.

Go skeleton

type TreeNode struct {
    Val         int
    Left, Right *TreeNode
}

func maxDepth(root *TreeNode) int {
    // BASE CASE
    // TODO: what's the depth of an empty tree?

    // RECURRENCE — trust the calls
    // TODO: combine the depths of left and right subtrees
    return 0
}

Three lines once you write it. The lever was the contract: once the contract is "depth of subtree", the recurrence falls out without thinking about stacks.

6 · Five-problem progression

7 · The "return one, track another" technique

Some tree problems require two pieces of information to bubble up: one is the recursion's return value, the other is updated as a side effect. This is the engine behind LC 124, the diameter problem (LC 543), and most tree-DP problems.

Reference: max path sum (LC 124)

Build the intuition: design two contracts

• What does the recursive call return, and what does it track on the side? Two separate things. Name them.
• Why can't the "answer" be the return value? A path through a node uses both children, but its parent can only extend through one. So the upward-returnable shape differs from the global-best shape.
• Why clip negative gains to zero? If a subtree's best downward gain is negative, we'd rather contribute 0 (skip the subtree) than reduce the sum.
• Where does the global answer get updated? At every node, because the optimal path could pass through any node, not just the root.

Go skeleton

func maxPathSum(root *TreeNode) int {
    answer := math.MinInt

    var gain func(n *TreeNode) int
    gain = func(n *TreeNode) int {
        if n == nil {
            return 0
        }
        // BEST downward gain from each side; clip negatives to 0
        left  := max(gain(n.Left),  0)
        right := max(gain(n.Right), 0)

        // CANDIDATE for the global answer:
        //   path that goes through n using BOTH sides
        // TODO: update answer

        // RETURN UPWARD:
        //   parent can only extend through ONE side
        // TODO: return n.Val + max(left, right)
        return 0
    }

    gain(root)
    return answer
}

func max(a, b int) int { if a > b { return a }; return b }

8 · Divide-and-conquer: merge sort and quickselect

Merge sort: Go template

func mergeSort(a []int) []int {
    if len(a) <= 1 {
        return a
    }
    mid := len(a) / 2
    left  := mergeSort(append([]int(nil), a[:mid]...))
    right := mergeSort(append([]int(nil), a[mid:]...))
    return merge(left, right)
}

func merge(a, b []int) []int {
    out := make([]int, 0, len(a)+len(b))
    i, j := 0, 0
    for i < len(a) && j < len(b) {
        if a[i] <= b[j] {
            out = append(out, a[i]); i++
        } else {
            out = append(out, b[j]); j++
        }
    }
    out = append(out, a[i:]...)
    out = append(out, b[j:]...)
    return out
}
// Time: O(n log n) — log n levels × O(n) per level
// Space: O(n) for the temporary slices

Quickselect (Kth largest, LC 215): Go skeleton

A pattern primitive: partition exactly like quicksort, but only recurse into the half that contains the kth element.

import "math/rand"

func kthLargest(nums []int, k int) int {
    a := append([]int(nil), nums...)     // don't mutate input
    target := len(a) - k                 // kth largest is index (n-k) after sort

    var quickSelect func(lo, hi int) int
    quickSelect = func(lo, hi int) int {
        if lo == hi {
            return a[lo]
        }

        // PIVOT — random pivot avoids O(n^2) worst case on sorted input
        pi := lo + rand.Intn(hi-lo+1)
        a[pi], a[hi] = a[hi], a[pi]
        pivot := a[hi]

        // PARTITION — Lomuto scheme; "store" is the boundary
        store := lo
        for i := lo; i < hi; i++ {
            // TODO: if a[i] < pivot, swap into the "smaller" partition; advance store
        }
        // TODO: move the pivot to its final position
        // TODO: compare store to target; recurse into the correct half
        return 0
    }

    return quickSelect(0, len(a)-1)
}
// Time: expected O(n); worst O(n^2) — pick random pivot
// Space: O(log n) expected (recursion stack)

Both follow the same template: split, recurse, combine. Merge sort combines all subresults; quickselect recurses into only one side. Quickselect is the canonical "skip the work you don't need" trick: O(n) expected versus O(n log n) for sort-then-pick.

Merge sort, drawn: split-and-merge tree

The tree has log₂ n levels (each split halves the size). At each level, every element is touched exactly once during the merge phase, so total work per level is O(n). Multiply: O(n log n) overall. The visualisation makes the recurrence T(n) = 2T(n/2) + O(n) concrete: two subproblems of size n/2 (the splits), O(n) combine (the merge).

9 · Memoisation: the bridge to DP

Naive Fibonacci is the textbook example of why pure recursion can be catastrophic. fib(n) calls itself twice; fib(n − 1) calls itself twice again; the call tree has 2ⁿ leaves at depth n. For n = 40, that's a trillion calls, and your interview machine times out.

Memoisation fixes this in three lines. Cache the result keyed by the arguments; on a repeat call, return the cached value instead of recursing. The call tree collapses from exponential to linear.

// Naive — exponential
func fibNaive(n int) int {
    if n < 2 {
        return n
    }
    return fibNaive(n-1) + fibNaive(n-2)
}
// T(n) = T(n-1) + T(n-2) + O(1) -> ~phi^n ≈ 1.618^n calls
// Time: O(2^n) · Space: O(n) (recursion stack)

// Memoised — linear (closure captures the cache)
func fibMemo(n int) int {
    memo := make(map[int]int)
    var f func(k int) int
    f = func(k int) int {
        if k < 2 {
            return k
        }
        if v, ok := memo[k]; ok {
            return v
        }
        v := f(k-1) + f(k-2)
        memo[k] = v
        return v
    }
    return f(n)
}
// Each unique argument computed once, served from cache thereafter
// Time: O(n) · Space: O(n)

// Bottom-up — same complexity, smaller constant, no recursion
func fibIter(n int) int {
    a, b := 0, 1
    for i := 0; i < n; i++ {
        a, b = b, a+b
    }
    return a
}
// Time: O(n) · Space: O(1)

From memoised recursion to DP: the conversion recipe

1. Write the recursion. State-form: solve(state) returns the answer for that state. The arguments are the state.
2. Add a cache. Decorate or wrap with a hash map keyed by state. Now you have memoised recursion.
3. (Optional) Convert to bottom-up. Iterate over states in dependency order; replace recursion with a table fill. Saves the recursion stack and often the cache space.

Many "hard DP" interview problems are actually easy memoised recursion problems. Start there. Convert to bottom-up only if asked, or if the recursion overflows. The pattern teaches itself once you've done five.

10 · Worked example: Maximum Path Sum (LC 124)

Given a binary tree, find the maximum sum of any path. A path can start and end at any nodes; can travel through internal nodes; can use both children of a node (going down-and-up through it). Negative node values allowed.

This problem is the canonical "return one thing, track another" tree problem. Two pieces of information bubble up: the global best path (updated as a side effect) and the best gain you can pass to a parent.

Trace through the tree below

         -10
        /   \
       9     20
            /  \
           15   7

Expected answer: 42 (path 15 → 20 → 7)

11 · Worked example: Merge K Sorted Lists (LC 23)

Two solutions, both worth knowing. The min-heap version is most common; the divide-and-conquer version is faster in practice and demonstrates the recursion-as-merge structure.

Build the intuition: choose your approach

• Approach 1: heap. Push the head of each list into a min-heap of size k. Pop the min, attach to output, push its successor. Repeat.
• Approach 2: divide-and-conquer. Pair up lists, merge each pair (you know how to merge two sorted lists). Recurse on the half-as-many lists until one remains.
• Same complexity, different constants. Both O(N log k). DC is typically ~1.3× faster because the per-element work is simpler (compare two pointers vs heap rebalance). Heap wins for streaming: you don't need all k lists upfront.

Go skeleton: divide-and-conquer (cleaner recursion)

type ListNode struct {
    Val  int
    Next *ListNode
}

// mergeTwo — you almost certainly know this one
func mergeTwo(a, b *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy
    for a != nil && b != nil {
        // TODO: append the smaller-headed list; advance it
    }
    // TODO: append whichever remains
    return dummy.Next
}

// mergeKLists — pair up and recurse
func mergeKLists(lists []*ListNode) *ListNode {
    var mergeRange func(lo, hi int) *ListNode
    mergeRange = func(lo, hi int) *ListNode {
        if lo > hi {
            return nil
        }
        if lo == hi {
            return lists[lo]
        }
        // TODO: split the range in half
        // TODO: recurse on each half
        // TODO: return mergeTwo of the two results
        return nil
    }
    return mergeRange(0, len(lists)-1)
}

Same complexity, but the divide-and-conquer is typically 1.3–1.5× faster on real inputs because the per-element work is simpler: no heap rebalancing, just comparing two pointers. The trade: the heap version handles streaming inputs (you don't need all k lists in memory upfront).

12 · Tail recursion & the accumulator pattern

A recursive call is in tail position if it's the last operation before the function returns, with no pending work after the call. In some languages (Scheme, Haskell, sometimes optimised by GCC), tail calls are converted to loops automatically, eliminating stack growth. Python and Java do not do this; tail recursion provides no stack savings on those platforms.

// Non-tail — multiplication is pending after the call
func factorialNaive(n int) int {
    if n <= 1 {
        return 1
    }
    return n * factorialNaive(n-1)
}

// Tail-shaped — the recursive call IS the last operation
// (Go does not optimise tail calls; this still grows the stack)
func factorialTail(n, acc int) int {
    if n <= 1 {
        return acc
    }
    return factorialTail(n-1, n*acc)
}

// In Go you'd typically just write the loop
func factorialIter(n int) int {
    acc := 1
    for i := 2; i <= n; i++ {
        acc *= i
    }
    return acc
}

The accumulator pattern is still useful even without tail-call optimisation: it makes the recursion's invariants explicit. The accumulator is what's been built so far; the rest of the input is what remains. This perspective is the foundation of how functional languages teach recursion.

When to convert to iteration

13 · Stack overflow in practice

A practical, often-asked-in-interviews scenario: a very deep tree (degenerate to a chain of 10⁵ nodes). Three responses:

• Just submit recursive. 10⁵ depth blows Python's default 1000-frame limit. Solution: sys.setrecursionlimit(10**6) at the top of main. Mention this aloud; interviewers respect the awareness even if not asked to convert.
• Convert to iterative DFS with explicit stack. Same algorithm, heap-allocated stack. Slightly faster in CPython because no per-call frame setup.
• Convert to BFS if depth is the issue. Sometimes BFS naturally bounds the queue to O(width) instead of O(depth). For balanced trees, that's huge.

// Iterative inorder — explicit stack, no recursion-depth bound
func inorderIter(root *TreeNode) []int {
    var stack []*TreeNode
    var out []int
    cur := root
    for len(stack) > 0 || cur != nil {
        // GO LEFT as far as you can
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }
        // POP and visit
        cur = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        out = append(out, cur.Val)
        // THEN go right (and repeat)
        cur = cur.Right
    }
    return out
}

// Same logic as recursive inorder; no recursion depth bound.
// Time: O(n) · Space: O(h) where h is tree height

14 · Sister algorithms

Recursion has a small cluster of related techniques that solve the problems pure recursion can't, usually because of stack depth, lack of tail-call optimisation, or the need to share state across branches. Knowing the names is enough to recognise them when an interviewer drops one casually.

• Memoisation (recursion + cache = top-down DP). The single most important upgrade to pure recursion. Wrap your recursive function in a cache keyed by its arguments; the first call computes; subsequent calls with the same args return the cached result. Converts exponential trees (naive Fibonacci, naive subset-sum) into polynomial ones (linear, pseudo-polynomial). In Go, the idiom is map[stateKey]int declared at the top of the outer function and read/written inside the closure. Cleaner than bottom-up DP when the dependency graph is irregular.
• Tail recursion (and why Go doesn't optimise it). A recursive call is in tail position if it's the very last operation before the function returns, with nothing pending after the call. In Scheme, Haskell, OCaml, and (sometimes) GCC's C with optimisation enabled, tail calls are converted to loops, so stack depth stays O(1). Go explicitly does not do this; it has clear language-design reasons (stack traces, panic recovery, and inlining all become trickier with TCO). The Go answer is "write the iterative version". Same for Python and Java. Don't rely on TCO for stack savings outside the functional family.
• Mutual recursion. Two (or more) functions call each other. Classical example: a recursive-descent parser where parseExpr calls parseTerm calls parseFactor calls parseExpr. Each function handles one grammar level; the cycle terminates when the input shrinks. Conceptually the same as ordinary recursion (they all share the call stack), but harder to memoise (the cache key must include which function is being called).
• Trampolining. A workaround for languages without TCO. Instead of recursing directly, the function returns a "thunk" (a thunk-returning function), and an outer loop (the "trampoline") repeatedly invokes it until a real result comes back. Converts unbounded recursion depth into a bounded stack. Used in Clojure's trampoline, JavaScript libraries that target deep recursion, and some Scheme implementations. Not idiomatic in Go (write iteration instead), but worth knowing when the question is "how would you do this in JavaScript without blowing the stack".
• Continuation-passing style (CPS). Instead of returning a value, every function takes an extra argument, a "continuation," which is called with what the result would have been. Transforms the program so that every operation is in tail position; combined with TCO, makes every program run in constant stack space. The basis of Scheme's call/cc, Haskell's monadic Cont, and the way browser JS engines used to do async before async/await. Beautiful and rarely needed; bring it up if an interviewer asks about implementing coroutines from scratch.
• Stack-to-queue iterative refactoring. The mechanical transformation from recursive DFS to iterative DFS uses a stack. Change the stack to a queue and you get BFS. This is why iterative DFS and BFS look almost identical: just one data-structure swap. Useful when the recursive form blows the stack on adversarial inputs (10⁵-deep linked-list-shaped trees) and you need a memory-safe version that handles the same algorithm.

15 · Worked example: LC 50 Pow(x, n) (recursive fast exponentiation)

Problem. Compute x^n for a floating- point x and a 32-bit integer n. Naive loop is O(n): two billion multiplications at n = 2^31, hopeless. Recursive fast exponentiation reduces to O(log n) using x^n = (x^(n/2))² when n is even.

Input:  x = 2.0, n = 10
Output: 1024.0

Input:  x = 2.0, n = -2
Output: 0.25
Explanation: 2^-2 = 1 / 2^2 = 0.25

The recurrence: three cases

The elegance: a single function with three branches.

• Base case. n == 0 → return 1 (anything to the 0 is 1).
• Negative case. n < 0 → return 1 / pow(x, -n). Flip the sign and invert the result.
• Even case. n even → compute half = pow(x, n/2), return half * half. One recursive call instead of two; this is the O(log n) magic.
• Odd case. n odd → return x * pow(x, n-1). Reduces to the even case in one step.

Go skeleton

func myPow(x float64, n int) float64 {
    if n == 0 {
        return 1
    }
    if n < 0 {
        return 1 / myPow(x, -n)
    }
    if n%2 == 0 {
        half := myPow(x, n/2)
        return half * half          // one call, not two
    }
    return x * myPow(x, n-1)        // odd: peel off one factor
}
// Time:  O(log n) — depth of recursion is log n
// Space: O(log n) for the recursion stack

// Iterative version (same complexity, no stack growth)
func myPowIter(x float64, n int) float64 {
    if n < 0 {
        x, n = 1/x, -n
    }
    result := 1.0
    for n > 0 {
        if n&1 == 1 {
            result *= x
        }
        x *= x
        n >>= 1
    }
    return result
}
// Time:  O(log n)
// Space: O(1)

Why "n/2" and not "n/2 + 1"

On an even n, x^n = (x²)^(n/2) = (x^(n/2))². On an odd n, you have to handle the dangling factor: the standard fix is to reduce to n - 1 (now even) and multiply by x once. The total depth of recursion is log₂ n (each "even" call halves n; the "odd" calls don't halve but always feed into an "even" call next, so they don't affect asymptotic depth).

16 · Worked example: LC 779 K-th Symbol in Grammar (recursion without materialising)

Problem. Row 1 of a grammar is "0". Row n is built from row n-1 by replacing every 0 with "01" and every 1 with "10". Given n (up to 30) and k (up to 2^(n-1)), return the k-th symbol (0-indexed) of row n.

Row 1: "0"
Row 2: "01"
Row 3: "0110"
Row 4: "01101001"

Input: n = 4, k = 4 (0-indexed)
Output: 1 (the 4th symbol of "01101001" is '1')

The naive solve fails: materialising row n is exponential

Row n has length 2^(n-1). At n = 30 that's 500 million bytes, out of memory. We need a way to find the k-th symbol without building the row.

The recursive insight

• Row n has length 2^(n-1). The first half (indices 0 to 2^(n-2) − 1) is identical to row n-1. The second half is the bitwise complement of row n-1 (each 0 → 01 contributes the second char, which is 1; each 1 → 10 contributes 0).
• The k-th symbol of row n:
  • If k < 2^(n-2): same as the k-th symbol of row n-1.
  • Otherwise: complement of the (k − 2^(n-2))-th symbol of row n-1.
• Base case. n = 1 → return 0 (row 1 is just "0").

Go skeleton

func kthGrammar(n, k int) int {
    if n == 1 {
        return 0
    }
    half := 1 << (n - 2)      // length of row n-1
    if k < half {
        return kthGrammar(n-1, k)
    }
    return 1 - kthGrammar(n-1, k-half) // complement
}
// Time:  O(n) — recursion depth, n up to 30
// Space: O(n) for the stack

// Equivalent — count set bits in k (parity trick)
// The k-th symbol of row n equals the popcount of k mod 2.
import "math/bits"

func kthGrammarBits(n, k int) int {
    return bits.OnesCount(uint(k)) & 1
}
// Time:  O(log k) — one POPCNT instruction on modern hardware
// Space: O(1)

Why the popcount trick works

Each level of recursion either keeps k in the first half (no flip) or moves to the second half and flips. The "flip" happens exactly when the high bit of k (relative to the current row) is set. After unwinding n levels, the answer has been flipped once per set bit of k, i.e., XOR-equivalent to popcount(k) mod 2. The recursive version is the pedagogical one; the popcount version is what you'd write in production.

17 · Worked example: LC 224 Basic Calculator (HARD: recursive-descent parser)

Problem. Evaluate a string expression containing non-negative integers, +, -, (, ), and spaces. No operator precedence beyond left-to- right and parentheses. Example: "(1+(4+5+2)-3)+(6+8)" evaluates to 23.

Why this is the canonical "recursion is parsing" problem

Parenthesised expressions are a recursive grammar. The natural implementation mirrors the grammar one-to-one: an expr is a sequence of terms joined by + or -; a term is either a number or a parenthesised expr. The parser walks the input with a shared cursor, calling itself when it sees ( and returning when it sees ). Stack-based iterative solutions exist, but the recursive version is shorter and reads like the grammar.

Go skeleton: recursive descent with a shared index

func calculate(s string) int {
    i := 0
    var parse func() int
    parse = func() int {
        result := 0
        sign := 1
        for i < len(s) {
            ch := s[i]
            switch {
            case ch == ' ':
                i++
            case ch >= '0' && ch <= '9':
                // Read the full number — could be multi-digit
                num := 0
                for i < len(s) && s[i] >= '0' && s[i] <= '9' {
                    num = num*10 + int(s[i]-'0')
                    i++
                }
                result += sign * num
            case ch == '+':
                sign = 1
                i++
            case ch == '-':
                sign = -1
                i++
            case ch == '(':
                i++                  // consume '('
                result += sign * parse()   // recurse on the inner expression
            case ch == ')':
                i++                  // consume ')'
                return result        // hand control back to the caller
            }
        }
        return result
    }
    return parse()
}
// Time:  O(n) — each character visited once
// Space: O(d) where d is the max parenthesis nesting depth

The two tricks that make this work

• The shared cursor. i is captured by closure across recursive calls. When the inner parse returns, the cursor has already advanced past the matching ). The outer call resumes from there.
• Sign tracking via a running variable. Instead of building an AST and evaluating, we accumulate result += sign * num as we go. sign resets to +1 after each operator, then flips to -1 if the operator is -. Works because there's no operator precedence to worry about.

18 · How to solve hard recursive problems, step-by-step

A discipline for working through any recursive problem, from the five-minute trees to the hour-long parsers. Five steps, in order:

1. Define the function's contract in one sentence. "f(x) returns the answer for subproblem x." Be specific: what does x represent? What does "answer" mean: a single value, a list, a tuple? Does f have side effects (mutating a shared variable, appending to an output list)? Write the contract as a comment at the top of the function before you write any code. If you can't fit it in one sentence, your problem decomposition is wrong; re-think the state.
2. Identify the base case(s). What's the smallest input that the contract handles trivially? Empty subtree, list of size 1, integer 0, boundary of grid. Write the base case as the first thing inside the function. If you can't write the base case in one or two lines, the contract is wrong; re-state it. Some problems have multiple base cases (n = 0 and n = 1 for Fibonacci); list them all.
3. Define the recursive step. How does f(x) compose from f(smaller)? Write the recursive call(s) assuming the contract holds for them. Don't trace; trust. The step is usually one line: return combine(f(sub1), f(sub2)), return f(rest) + this_contribution, or similar. If the step needs more than three lines, you're probably mixing the recurrence with the combine logic; separate them.
4. Verify with a small example by hand. Pick the smallest non-trivial input (n = 2 or n = 3, or a tree with 3 nodes). Trace base + step. Does it produce the right answer? If yes, induction takes care of the rest. If no, the bug is in the base, the step, or the contract; work out which before adding more code.
5. Consider memoisation if there's overlap. Print or count the recursive calls for a moderate input (n = 8 or so). If the same arguments appear multiple times, memoise: add a map[stateKey]ResultT, return cached values when present. Don't optimise prematurely; pure recursion is fine for tree traversal (no overlap by construction) and for generation problems (each call has unique state). Memoise only when the call tree has duplicates.

19 · Master Theorem cheat sheet

The Master Theorem gives the asymptotic solution to recurrences of the form T(n) = a·T(n/b) + f(n), where:

• a = number of subproblems per call (the branching factor).
• b = factor by which the subproblem size shrinks (usually 2).
• f(n) = work done at each call outside the recursive calls (the "combine" step).

The solution depends on how f(n) compares to n^(log_b a), the "watershed" exponent. Three cases:

Concrete examples worth memorising

20 · Common pitfalls

• No base case. Stack overflow. Most languages cap at ~1000 frames; Python's default is 1000. Always start by writing the base case.
• Wrong base case. "An empty tree has depth -1" instead of 0. Re-derive carefully; the base case must satisfy the recurrence at the boundary.
• Modifying shared state without restoring. Backtracking bug. path.append(x); recurse(); path.pop(): pop is mandatory.
• Returning the wrong thing. The classic LC 124 bug: returning val + left + right instead of val + max(left, right). The "return upward" path differs from the "candidate global answer" path.
• Forgetting the trust principle. Tracing the call stack in your head. Stop. State the contract; trust the call.
• Stack overflow on deep recursion. Python: sys.setrecursionlimit(10**6). Better: convert to iterative if the input can be 10⁶ deep.
• Recomputing the same subproblem. the Fibonacci trap, where naive recursion is exponential. Memoise or convert to DP.
• Off-by-one in slicing. Merge sort: a[:mid] and a[mid:], never a[:mid] and a[mid+1:] (drops the middle element). Quickselect: store + 1 after partition, not store.
• Stack overflow on deep recursion: language-specific limits. Go's goroutine stacks start at 8 KB and grow up to 1 GB by default, so deep recursion almost never overflows on Go, but on a heavily recursive function with large stack frames (multi-megabyte locals), you can hit the 1 GB limit on 10⁴–10⁵ deep inputs. Python's default sys.setrecursionlimit(1000) catches you at 1000 frames; bump with sys.setrecursionlimit(10**6) for competitive programming. Java's default thread stack is 512 KB or 1 MB; deep recursion (10⁴ frames with moderate locals) trips a StackOverflowError. JavaScript V8 caps at ~10,000–15,000 frames. Know your platform's limit before submitting.
• Not establishing a clear contract leads to spaghetti code. The number one bug in junior recursion code is "I have a function that does several things and I'm not quite sure what". Symptoms: parameters that aren't used in every branch, return values that mean different things in different branches, side effects mixed with returns. Fix: write the contract as a comment first, then code only to it. If a parameter isn't part of the contract, it shouldn't be there.
• Mutating shared state across recursive calls without restoring it. The backtracking trap. If you have a shared path []int or visited map[int]bool and you mutate it before recursing, you MUST undo the mutation after the recursive call returns. path = append(path, x); recurse(); path = path[:len(path)-1]. The push-pop must always be symmetric; forget the pop and a sibling branch sees state from the parent's earlier child.
• Forgetting the base case entirely. Stack overflow. The compiler does not warn you. Always start by writing the base case before the recursive step; this is also why a one-sentence contract helps: if you can state the contract, you can state the smallest input that satisfies it trivially, which is your base case.
• Recursing on the same problem rather than a strictly smaller one. Infinite recursion. The recursive call must take a strictly smaller argument (smaller tree, shorter string, fewer items remaining). If you call f(x) from inside f(x) or pass an argument that doesn't monotonically decrease, the recursion never terminates. Trace the first three or four calls in your head; if the argument isn't getting smaller, your recursion is broken.

21 · Recursion-to-iteration mechanical conversion

When the input may be deep enough to blow the stack (typical threshold ~10⁵ depth), convert recursion to an explicit stack (or queue, for BFS). The transformation is mechanical:

// Recursive in-order
func inorder(n *TreeNode, out *[]int) {
    if n == nil {
        return
    }
    inorder(n.Left, out)
    *out = append(*out, n.Val)
    inorder(n.Right, out)
}

// Iterative equivalent — explicit stack, no recursion depth bound
func inorderIterative(root *TreeNode) []int {
    var stack []*TreeNode
    var out []int
    cur := root
    for len(stack) > 0 || cur != nil {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }
        cur = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        out = append(out, cur.Val)
        cur = cur.Right
    }
    return out
}

The iterative version's complexity matches the recursive one (same time, same space), but uses heap-allocated stack rather than the OS stack. Faster in practice on most JIT'd runtimes; required for very deep trees.

22 · Complexity (the master theorem, briefly)

For divide-and-conquer recurrences T(n) = a·T(n/b) + f(n):

For interviews, recognise the four common shapes (lines 1, 3, 4, 5). The full master theorem is overkill on a whiteboard.

23 · Variants & related patterns

• Dynamic programming. "Memoise the recursion." DP is recursion with a cache.
• Backtracking. Recursion + undo. The "try every option" pattern.
• DFS. Recursion with a visited set, applied to graphs.
• Tree DP. The "return one, track another" technique generalised.
• Tail recursion. Some compilers optimise; most don't (Python and Java don't). Don't rely on it for stack savings.
• Adjacent: recursion simulator. Visualise the call tree filling in.
• Adjacent: balanced-tree simulator. See recursion working on actual tree structures.

24 · Where this gets asked

25 · Try it yourself

Invert Binary Tree · LC 226

The three-line recursion drill. Hint: root.left, root.right = invert(root.right), invert(root.left), then return root. Trust that the recursion handles the subtrees correctly.

Diameter of Binary Tree · LC 543

The "return one, track another" warm-up. Hint: helper returns the DEPTH of a subtree; track the global maximum of left_depth + right_depth as a closure variable. Don't return the diameter itself.

Lowest Common Ancestor · LC 236

The recursive contract is the whole problem. Hint: return root if root == p or root == q. Recurse left and right. If both sides return non-null, this node is the LCA; else return whichever side is non-null.

Binary Tree Maximum Path Sum · LC 124

The masterclass for "return one, track another". Hint: helper returns the BEST DOWNWARD GAIN (one side only, clipped to 0). Track the global max of node.val + left_gain + right_gain at each node.

Stretch: Serialize and Deserialize Binary Tree · LC 297

Two mirrored recursions. Hint: serialize uses pre-order with a null sentinel; deserialize consumes the same stream, builds left then right recursively. The trick: deserialize needs a mutable iterator so each call consumes from the shared stream.

Further reading

• CLRS — Introduction to Algorithms, Chapter 4. Recurrences, master theorem, substitution method. The reference.
• SICP — Structure and Interpretation of Computer Programs, Chapter 1.2. The classic introduction to recursion as a way of thinking, not just a control flow.
• Hoare — "Quicksort" (1962). The original divide-and-conquer paper. Still readable, still beautiful.
• von Neumann — Internal report on merge sort (1945). The first divide-and-conquer algorithm in print.
• Dijkstra — "Recursive programming" (1960). The original case for recursion as a first-class control-flow primitive.
• Adjacent: the methodology page. Spaced repetition for the reps that build the trust principle.
• Adjacent: Go internals. Go's stack growth, relevant if you write recursion that may grow large.