07. Recursion

Recursion is a function calling itself to solve a smaller version of the same problem. It's not a data structure — it's a problem-solving technique that underpins trees, graphs, backtracking, and dynamic programming. If you don't understand recursion, those topics will feel like magic.

The Two Parts

Every recursive function needs:

1. Base case — the trivial answer that stops recursion
2. Recursive case — break the problem into a smaller version and call yourself

// Factorial: n! = n × (n-1)!
func factorial(n int) int {
    if n <= 1 {
        return 1 // base case
    }
    return n * factorial(n-1) // recursive case
}

Without a base case, recursion runs forever (stack overflow). Without a recursive case, you're just writing an if statement.

The Call Stack

Each recursive call pushes a new frame onto the call stack. The frame holds local variables and the return address. When the base case returns, frames pop off one by one.

factorial(4)
  → factorial(3)
    → factorial(2)
      → factorial(1)
      ← returns 1
    ← returns 2 × 1 = 2
  ← returns 3 × 2 = 6
← returns 4 × 6 = 24

Stack depth = number of nested calls. For factorial(n), depth is n. If n is too large, you get a stack overflow. Go's default goroutine stack starts at 8KB but grows dynamically — still, deep recursion (millions of levels) can be a problem.

The Recursive Leap of Faith

Don't trace every call mentally. Instead, trust that the recursive call returns the correct answer for the smaller problem, then use that to build the answer for the current problem.

// Sum of a list: trust that sum(rest) works, then add the first element
func sum(nums []int) int {
    if len(nums) == 0 {
        return 0 // base case
    }
    return nums[0] + sum(nums[1:]) // first + sum of rest
}

You don't need to trace sum([1,2,3,4]) → sum([2,3,4]) → ... Just trust: "if sum(nums[1:]) gives me the sum of everything except the first element, then adding nums[0] gives me the total."

Recursion on Trees

Trees are naturally recursive — every subtree is itself a tree. This is why most tree problems use recursion.

// Count nodes in a binary tree
func countNodes(root *TreeNode) int {
    if root == nil {
        return 0 // base case: empty tree has 0 nodes
    }
    return 1 + countNodes(root.Left) + countNodes(root.Right)
}

The pattern: handle nil (base case), then combine results from left and right subtrees.

Recursion on Linked Lists

// Reverse a linked list recursively
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head // base case: 0 or 1 node
    }
    newHead := reverseList(head.Next) // reverse the rest
    head.Next.Next = head             // point next node back to me
    head.Next = nil                   // I'm now the tail
    return newHead
}

Multiple Recursive Calls

Some problems make more than one recursive call per frame. This creates a tree of calls.

// Fibonacci — two recursive calls per frame
func fib(n int) int {
    if n <= 1 {
        return n
    }
    return fib(n-1) + fib(n-2) // O(2ⁿ) without memoization!
}

Two calls per level means exponential growth. This is where memoization (DP) comes in — cache results to avoid recomputation.

Recursion vs Iteration

Any recursion can be converted to iteration using an explicit stack. Recursion is often cleaner for tree/graph problems; iteration avoids stack overflow for deep problems.

// Recursive DFS
func dfs(node *TreeNode) {
    if node == nil {
        return
    }
    fmt.Println(node.Val) // process current node (e.g., print, collect, check)
    dfs(node.Left)
    dfs(node.Right)
}

// Iterative equivalent
func dfsIterative(root *TreeNode) {
    stack := []*TreeNode{root}
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if node == nil {
            continue
        }
        fmt.Println(node.Val) // process current node
        stack = append(stack, node.Right)
        stack = append(stack, node.Left)
    }
}

When to use recursion: tree problems, divide-and-conquer, backtracking, when the recursive solution is clearer.

When to use iteration: deep recursion (risk of stack overflow), performance-critical code, simple loops.

Common Mistakes

1. Missing base case — infinite recursion, stack overflow
2. Base case doesn't cover all terminal states — e.g., checking n == 0 but not n < 0
3. Not making the problem smaller — recursive call must move toward the base case
4. Modifying shared state incorrectly — forgetting to undo changes (backtracking)

Practice Problems

Key Takeaways

• Every recursive function needs a base case (stop) and a recursive case (shrink and call)
• The call stack tracks each frame — depth equals the number of nested calls
• Use the recursive leap of faith: trust the recursive call works, build on its result
• Trees are naturally recursive — most tree solutions follow: handle nil, combine left + right
• Multiple recursive calls per frame → exponential time unless you memoize
• Any recursion can become iteration with an explicit stack
• Recursion is the foundation for trees, graphs, backtracking, and DP