Pattern #20

Recursion

Important interview questions, thinking patterns, base cases, call stack mechanics, and rules for solving recursive problems in Go.

Must Solve

18 core questions — solve these first.

1.Factorial
Base n <= 1, return n * factorial(n-1)easy
2.Fibonacci Number
Base n <= 1, fib(n-1) + fib(n-2)easy
3.Pow(x, n)
Divide & Conquer exponentiation by halvingmedium
4.Reverse String
Swap outer chars recursivelyeasy
5.Palindrome Check
Base len <= 1, check S[0] == S[len-1]easy
6.Binary Search using Recursion
Divide range mid +/- 1easy
7.Merge Two Sorted Lists
Recursive list mergingeasy
8.Reverse Linked List
head.Next.Next = head; head.Next = nileasy
9.Maximum Depth of Binary Tree
1 + max(depth(Left), depth(Right))easy
10.Same Tree
p.Val == q.Val && isSame(Left) && isSame(Right)easy
11.Invert Binary Tree
Swap Left & Right children recursivelyeasy
12.Path Sum
Subtract val from targetSum down to leafeasy
13.Generate Parentheses
Backtracking recursion open/close countmedium
14.Subsets
Include / exclude recursion treemedium
15.Permutations
Swap / visited backtracking recursionmedium
16.Combination Sum
Choose element multiple times recursionmedium
17.Letter Combinations of a Phone Number
Digit index string mapping recursionmedium
18.Word Search
Grid DFS 4-directional recursion + backtrackingmedium

Also Important

9 more questions worth practicing.

19.Climbing Stairs
Fibonacci recursion + Memoizationeasy
20.K-th Symbol in Grammar
Parent character binary flip recursionmedium
21.Swap Nodes in Pairs
Swap head & head.Next recursivelymedium
22.Decode String
Parse nested multiplier strings recursivelymedium
23.Different Ways to Add Parentheses
Split expression by operator Divide & Conquermedium
24.Unique Paths
Grid DFS (down + right) + Memoizationmedium
25.N-Queens
Row-by-row board placement backtrackinghard
26.Sudoku Solver
Grid cell 1-9 trial & validation recursionhard
27.Tower of Hanoi
Move N-1 to temp, 1 to target, N-1 to targetmedium

How to Think

Can problem become a smaller same problem?Recursion
Tree problem?Recursion
Need try all choices?Recursion + Backtracking
Need divide problem into smaller parts?Recursion (Divide & Conquer)
Same work repeats many times?Recursion + Memoization

Recursive Thinking Template & Go Example

3 Golden Questions for Every Recursive Function:

What does my function mean? (e.g. maxDepth(node))
What is the smallest / Base Case? (node == nil -> 0)
How do I reduce the problem? (1 + max(left, right))

func maxDepth(root *TreeNode) int {
    // 1. Base Case (stops recursion)
    if root == nil {
        return 0
    }

    // 2. Reduce Problem (subproblems for left & right children)
    leftDepth := maxDepth(root.Left)
    rightDepth := maxDepth(root.Right)

    // 3. Return answer back upward
    return 1 + max(leftDepth, rightDepth)
}

👉 Calls go DOWN call stack → Answers return UPWARD

Two Essentials Every Recursion Needs

1. Base Case

if n <= 1 { return 1 }

Stops recursion. Without a base case, the function calls itself infinitely until stack overflow crash!

2. Smaller Problem

factorial(n) -> factorial(n-1)

Each recursive call must move strictly closer toward the stopping base case.

Recursion vs Iteration

Recursion calls itself (using the call stack), while iteration uses explicit loops (for / while).

Use Recursion when problem structure is naturally recursive:

Binary TreesGraph DFSBacktrackingDivide & Conquer

Visual Memory Rule

Call  →  Smaller Problem  →  Base Case  →  Return Answer Upward
Tree/DFS     →  Recursion
All choices  →  Recursion + Backtracking
Repeated     →  Memoization

💡 Golden Rule: "Define what one recursive call should solve, make the problem smaller, and trust the next call to solve the rest."

Common Interview Mistakes

1. Missing Base Case

Forgetting base case condition leads directly to infinite recursion and stack overflow crashes!

2. Base Case Checked Too Late

Dereferencing node fields (node.Val) before checking node == nil causes null pointer panics.

3. Forgetting Return Value

Calling dfs(child) without saving or returning its result ignores critical subproblem answers.

4. Ignoring Call Stack Space

Recursion uses implicit call stack space (O(depth)) even without allocating explicit arrays.

Interview Rules

1. Tree problem? → Think Recursion
2. DFS traversal? → Recursion fits naturally
3. Try every choice? → Recursion + Backtracking
4. Base case required first to specify stopping condition
5. Every call must reduce problem size toward base case
6. Call stack space = O(recursion depth)
7. Deep recursion risk → Watch out for stack overflow on massive inputs
8. Repeated subproblems? → Use Memoization cache
9. Multiple branching calls (e.g. fib(n-1) + fib(n-2)) → Watch out for exponential time O(2^N)

Small Rules

Rule 1: Always find and write the base case first.
Rule 2: Each call must move strictly toward stopping (e.g. n-1).
Rule 3: Recursion implicitly consumes O(depth) memory on call stack.
Rule 4: Two branching calls without memoization cause O(2^N) exponential explosion.
Rule 5: Always calculate the total number of function calls to determine time complexity.

Production Thinking

Nested Folder Traversal → Visit directory & recursively process nested subfolders

JSON / AST Parsing → Traverse arbitrarily nested JSON objects & abstract syntax trees

UI Component Trees → React Virtual DOM rendering & event bubbling up component tree

Package Dependency Resolution → Walk package dependency trees with cycle detection guard

Production Stack Overflow Safety → Prefer iterative loops for extremely deep structures (millions of items)

Remember This

Recursion            → function calls itself
Must have            → base case
Each call            → smaller problem
Calls                → go down
Answers              → come back up
Tree / DFS           → recursion
All choices          → recursion + backtracking
Repeated work        → memoization
Very deep calls      → stack risk

💡 Golden Rule: "Define what one recursive call should solve, make the problem smaller, and trust the next call to solve the rest."