There's a moment in every developer's journey where recursion shows up and just... breaks your brain. You're sitting there, staring at a function that calls itself, trying to mentally trace what happens, and somewhere around the third level deep your internal stack overflows. The function calls itself, which calls itself, which calls itself, and now you're holding five return values in your head at once and your eyes are glazing over. You close the tab. You Google "recursion explained simply." The top result uses recursion to explain recursion. Helpful. Here's the thing: recursion isn't inherently hard. It's *unfamiliar*. Our brains think in loops. We think step-by-step, start here, do this, then that, repeat. Recursion asks us to think differently, to trust that a smaller version of the same problem will solve itself, and to just handle the simplest case. That mental shift is what trips people up, not the code itself. But once recursion clicks? It unlocks *everything*. Trees, graphs, backtracking, dynamic programming, divide and conquer, nearly every advanced algorithm topic assumes you're comfortable with recursion. It's the gateway skill. And the good news is: it's a skill you can absolutely build, one step at a time. > "To understand recursion, you must first understand recursion." — Every CS professor, thinking they're hilarious. This guide is going to take you from "I sort of get it but can't write it" to "I think recursively now." We'll start from scratch, visualize what's actually happening under the hood, solve real problems, and build the intuition you need to reach for recursion with confidence. Let's break it down. --- ## What Is Recursion? At its simplest, **recursion** is when a function calls itself to solve a smaller version of the same problem. That's it. That's the whole concept. A function that calls itself. But there's a catch, and it's the most important rule in all of recursion: > Every recursive function **must** have a base case, a condition where it stops calling itself and returns a value directly. Without a base case, you get infinite recursion, which leads to a **stack overflow**, which leads to your program crashing, which leads to existential dread. We'll get to that in a moment. ### The Two Rules of Recursion 1. **Base case**: The condition where the function stops recursing and returns a direct answer. 2. **Recursive case**: The part where the function calls itself with a *smaller* or *simpler* input, moving closer to the base case. That's the entire framework. Every recursive function you'll ever write follows this structure. ### The Russian Nesting Doll Analogy Think of a set of Russian nesting dolls (matryoshka). You open the outer doll and find a smaller doll inside. You open that one and find an even smaller one. You keep opening until you reach the tiniest doll that doesn't open, that's your **base case**. Then you start putting them back together, building up the answer as you return from each level. Or think of it like this: you're standing between two mirrors facing each other. You see yourself reflected infinitely. But if someone puts a curtain over one mirror at a certain depth, the reflections stop. That curtain is the base case. ### A Simple Example: Counting Down ```typescript function countdown(n: number): void { if (n <= 0) { console.log("Done!"); return; } console.log(n); countdown(n - 1); } countdown(5); // 5, 4, 3, 2, 1, Done! ``` - **Base case**: `n <= 0` → print "Done!" and stop. - **Recursive case**: print `n`, then call `countdown(n - 1)`. Each call reduces `n` by 1, getting closer to the base case. Simple, predictable, and it terminates. That's recursion working correctly. --- ## The Call Stack Visualized Understanding the **call stack** is the key to truly grasping recursion. Without it, recursive functions feel like magic. With it, they feel mechanical. ### What Is the Call Stack? The **call stack** is a data structure that your JavaScript/TypeScript runtime uses to keep track of function calls. Every time a function is called, a new **stack frame** is pushed onto the stack. When a function returns, its frame is popped off. It's literally a stack: last in, first out (LIFO). When you call a recursive function, each call adds a new frame to the stack. The function doesn't "forget" where it was, each frame holds its own local variables, its own arguments, and knows where to return to. ### Walking Through the Stack Let's trace through a simple example: summing numbers from 1 to `n`. ```typescript function sumTo(n: number): number { if (n <= 0) return 0; return n + sumTo(n - 1); } console.log(sumTo(4)); // 10 ``` Here's what happens on the call stack, step by step: ``` Call: sumTo(4) → 4 + sumTo(3) Call: sumTo(3) → 3 + sumTo(2) Call: sumTo(2) → 2 + sumTo(1) Call: sumTo(1) → 1 + sumTo(0) Call: sumTo(0) → returns 0 ← base case hit! returns 1 + 0 = 1 returns 2 + 1 = 3 returns 3 + 3 = 6 returns 4 + 6 = 10 ``` Think of it like stacking plates. Each call puts a new plate on top. You can't get to the bottom plate until you remove all the plates above it. The base case is when you stop adding plates and start removing them. ### Visualizing the Stack Frames At the deepest point of `sumTo(4)`, the call stack looks like this: ``` ┌─────────────┐ │ sumTo(0) │ ← top of stack (base case, about to return) ├─────────────┤ │ sumTo(1) │ waiting for sumTo(0) to return ├─────────────┤ │ sumTo(2) │ waiting for sumTo(1) to return ├─────────────┤ │ sumTo(3) │ waiting for sumTo(2) to return ├─────────────┤ │ sumTo(4) │ waiting for sumTo(3) to return ├─────────────┤ │ main() │ ← bottom of stack └─────────────┘ ``` Each frame is frozen in time, waiting for the call above it to finish. Once `sumTo(0)` returns `0`, the frames start resolving from top to bottom. ### What Happens Without a Base Case? ```typescript function oops(n: number): number { return n + oops(n - 1); // no base case! } ``` This never stops calling itself. The stack grows and grows until the engine hits its limit: ``` RangeError: Maximum call stack size exceeded ``` That's a **stack overflow**. The stack ran out of room. This is why the base case isn't optional, it's *essential*. Every recursive function must guarantee it eventually stops. > The call stack is finite. Every recursive call costs a stack frame. Always ensure your recursion terminates. --- ## The Anatomy of a Recursive Function Now that you know what the call stack does, let's formalize the structure every recursive function follows. Once you internalize this template, writing recursive functions becomes a fill-in-the-blanks exercise. ### The Template ```typescript function recurse(input: InputType): ReturnType { // 1. Base case: the simplest version of the problem if (baseCondition) { return baseValue; } // 2. Recursive case: break the problem into a smaller piece // and combine the result return combine(currentWork, recurse(smallerInput)); } ``` ### Breaking It Down **Step 1: Identify the base case.** Ask yourself: "What is the simplest possible input? What should the answer be for that input?" - For a number counting down: `n <= 0` - For an array: an empty array `[]` - For a string: an empty string `""` - For a tree: a `null` node **Step 2: Identify the recursive case.** Ask: "How can I break this problem into a smaller version of itself?" - For a number: use `n - 1` - For an array: use `arr.slice(1)` (the rest of the array) - For a string: use `str.slice(1)` (everything after the first character) - For a tree: use `node.left` and `node.right` **Step 3: Combine.** How do you combine the current step's work with the recursive result? - Add the current number to the sum of the rest - Prepend the current character to the reversed rest - Merge the current node with the results from children ### A Concrete Example Let's find the maximum value in an array recursively: ```typescript function findMax(arr: number[]): number { if (arr.length === 1) return arr[0]; const maxOfRest = findMax(arr.slice(1)); return arr[0] > maxOfRest ? arr[0] : maxOfRest; } console.log(findMax([3, 7, 2, 9, 1])); // 9 ``` - **Base case**: array has one element → that element is the max. - **Recursive case**: compare the first element with the max of the rest. - **Combine**: return whichever is larger. > When stuck writing a recursive function, always start by answering: "What's the base case?" and "How does the input get smaller?" Everything else flows from there. --- ## Classic Warm-ups with TypeScript Time to get your hands dirty. These are the fundamental recursive problems that every developer should be comfortable with. Each one reinforces the core pattern: base case, recurse on something smaller, combine. --- ### 1. Factorial The factorial of `n` (written `n!`) is the product of all positive integers up to `n`. For example, `5! = 5 × 4 × 3 × 2 × 1 = 120`. This is the "hello world" of recursion. ```typescript function factorial(n: number): number { if (n <= 1) return 1; return n * factorial(n - 1); } console.log(factorial(5)); // 120 console.log(factorial(0)); // 1 console.log(factorial(10)); // 3628800 ``` **How it works:** - **Base case**: `n <= 1` → return `1` (0! and 1! are both 1). - **Recursive case**: `n * factorial(n - 1)`. - Each call multiplies `n` by the factorial of the number below it, building up the answer as the stack unwinds. **Trace for `factorial(4)`:** ``` factorial(4) → 4 * factorial(3) factorial(3) → 3 * factorial(2) factorial(2) → 2 * factorial(1) factorial(1) → 1 ← base case returns 2 * 1 = 2 returns 3 * 2 = 6 returns 4 * 6 = 24 ``` **Complexity:** - Time: **O(n)** — one call per decrement from `n` to `1`. - Space: **O(n)** — `n` frames on the call stack. --- ### 2. Fibonacci The Fibonacci sequence: `0, 1, 1, 2, 3, 5, 8, 13, 21, ...` Each number is the sum of the two before it. ```typescript function fibonacci(n: number): number { if (n <= 0) return 0; if (n === 1) return 1; return fibonacci(n - 1) + fibonacci(n - 2); } console.log(fibonacci(0)); // 0 console.log(fibonacci(6)); // 8 console.log(fibonacci(10)); // 55 ``` **How it works:** - **Base cases**: `fib(0) = 0`, `fib(1) = 1`. - **Recursive case**: `fib(n) = fib(n-1) + fib(n-2)`. This is elegant, but there's a problem. Let's look at the call tree for `fibonacci(5)`: ``` fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1) / \ / \ / \ fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) / \ fib(1) fib(0) ``` See the problem? `fib(3)` is calculated twice. `fib(2)` is calculated three times. The amount of redundant work **explodes** as `n` grows. **Complexity (naive):** - Time: **O(2ⁿ)** — exponential. Each call branches into two. - Space: **O(n)** — the maximum depth of the call stack. #### The Fix: Memoization We can cache results to avoid recalculating the same values: ```typescript function fibonacciMemo( n: number, memo: Map = new Map() ): number { if (n <= 0) return 0; if (n === 1) return 1; if (memo.has(n)) return memo.get(n)!; const result = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo); memo.set(n, result); return result; } console.log(fibonacciMemo(50)); // 12586269025 ``` Now each value of `n` is calculated only once and looked up from the cache after that. **Complexity (memoized):** - Time: **O(n)** — each subproblem solved once. - Space: **O(n)** — for the memo cache and call stack. > Memoization is the bridge between recursion and dynamic programming. We'll cover DP in depth in a future article, but know that it starts here. --- ### 3. Sum of an Array A great example of recursion on a data structure rather than a number. ```typescript function sumArray(arr: number[]): number { if (arr.length === 0) return 0; return arr[0] + sumArray(arr.slice(1)); } console.log(sumArray([1, 2, 3, 4, 5])); // 15 console.log(sumArray([])); // 0 ``` **How it works:** - **Base case**: empty array → return `0`. - **Recursive case**: first element + sum of the rest. - Each call peels off the first element and recurses on the remaining array. **Trace for `sumArray([1, 2, 3])`:** ``` sumArray([1, 2, 3]) → 1 + sumArray([2, 3]) sumArray([2, 3]) → 2 + sumArray([3]) sumArray([3]) → 3 + sumArray([]) sumArray([]) → 0 returns 3 + 0 = 3 returns 2 + 3 = 5 returns 1 + 5 = 6 ``` **Complexity:** - Time: **O(n)** — one call per element. - Space: **O(n)** — call stack depth plus the sliced arrays. > Note: `arr.slice(1)` creates a new array each time, adding O(n) work per call. For interview optimization, you'd pass an index instead. But for learning, this is clearer. Here's the index-based version for reference: ```typescript function sumArrayOptimized(arr: number[], index: number = 0): number { if (index >= arr.length) return 0; return arr[index] + sumArrayOptimized(arr, index + 1); } ``` --- ### 4. Reverse a String ```typescript function reverseString(str: string): string { if (str.length <= 1) return str; return reverseString(str.slice(1)) + str[0]; } console.log(reverseString("hello")); // "olleh" console.log(reverseString("a")); // "a" console.log(reverseString("")); // "" ``` **How it works:** - **Base case**: string is empty or one character → return it as-is. - **Recursive case**: reverse everything after the first character, then append the first character at the end. **Trace for `reverseString("cat")`:** ``` reverseString("cat") → reverseString("at") + "c" reverseString("at") → reverseString("t") + "a" reverseString("t") → "t" ← base case returns "t" + "a" = "ta" returns "ta" + "c" = "tac" ``` **Complexity:** - Time: **O(n²)** — `n` calls, and string concatenation is O(n) in the worst case. - Space: **O(n)** — call stack depth. > For production code, you'd reverse a string iteratively or use `str.split('').reverse().join('')`. But this exercise builds the recursive muscle. --- ### 5. Exponentiation (Power) Calculate `base^exponent` recursively. This one also introduces a neat optimization. ```typescript function power(base: number, exp: number): number { if (exp === 0) return 1; return base * power(base, exp - 1); } console.log(power(2, 10)); // 1024 console.log(power(3, 4)); // 81 ``` **Complexity (naive):** - Time: **O(n)** where n is the exponent. - Space: **O(n)**. #### Fast Power (Exponentiation by Squaring) We can cut the work in half at each step: ```typescript function fastPower(base: number, exp: number): number { if (exp === 0) return 1; if (exp % 2 === 0) { const half = fastPower(base, exp / 2); return half * half; } return base * fastPower(base, exp - 1); } console.log(fastPower(2, 10)); // 1024 console.log(fastPower(2, 20)); // 1048576 ``` - If the exponent is even: `base^n = (base^(n/2))²` - If it's odd: `base^n = base * base^(n-1)` **Complexity (fast):** - Time: **O(log n)** — we halve the exponent each step. - Space: **O(log n)** — call stack depth. > This is the same principle behind many divide-and-conquer algorithms. Cutting the problem in half at each step gives you logarithmic performance. --- ## Recursion vs Iteration Every recursive function can be rewritten iteratively, and vice versa. So when should you choose one over the other? ### The Same Problem, Two Ways Let's compare factorial both ways: **Recursive:** ```typescript function factorialRecursive(n: number): number { if (n <= 1) return 1; return n * factorialRecursive(n - 1); } ``` **Iterative:** ```typescript function factorialIterative(n: number): number { let result = 1; for (let i = 2; i <= n; i++) { result *= i; } return result; } ``` Both produce the same result. Both are O(n) in time. But the iterative version uses O(1) space (no call stack buildup), while the recursive version uses O(n) space. ### When to Use Recursion | Use Recursion When... | Use Iteration When... | |---|---| | The problem has natural subproblem structure | The logic is a straightforward loop | | You're working with trees, graphs, or nested data | You need tight control over memory | | The recursive solution is dramatically simpler | Performance is critical and stack depth is a concern | | You're doing backtracking or generating combinations | The iterative version is equally readable | | Divide-and-conquer is the natural strategy | You're processing a flat, linear data structure | ### Pros and Cons | | Recursion | Iteration | |---|---|---| | **Readability** | Often cleaner for complex problems | Cleaner for simple loops | | **Stack space** | O(n) or O(log n) depending on depth | O(1) typically | | **Risk** | Stack overflow for deep recursion | No stack overflow risk | | **Debugging** | Harder to trace | Easier to step through | | **Natural fit** | Trees, graphs, nested structures | Arrays, counters, sequences | ### Converting Recursion to Iteration Any recursive function can be converted to iteration using an explicit stack. Here's `sumTo` both ways: **Recursive:** ```typescript function sumToRecursive(n: number): number { if (n <= 0) return 0; return n + sumToRecursive(n - 1); } ``` **Iterative with explicit stack:** ```typescript function sumToIterative(n: number): number { const stack: number[] = []; let current = n; while (current > 0) { stack.push(current); current--; } let total = 0; while (stack.length > 0) { total += stack.pop()!; } return total; } ``` Of course, for summing numbers you'd just use a simple loop. But the pattern of replacing the call stack with an explicit stack is how you convert *any* recursive function to iteration, and it's especially useful for tree/graph traversals where recursion depth might be dangerous. > When the recursive version is clear and the depth is bounded, prefer recursion. When depth could be huge or you need maximum performance, convert to iteration. --- ## Tail Recursion You might have heard the term **tail recursion** and wondered if it's something you need to care about. Let's demystify it. ### What Is Tail Recursion? A function is **tail recursive** if the recursive call is the very last thing the function does, with no additional work after the call returns. **Not tail recursive** (has work after the recursive call): ```typescript function factorial(n: number): number { if (n <= 1) return 1; return n * factorial(n - 1); // multiplication happens AFTER the recursive call returns } ``` **Tail recursive** (the recursive call is the final operation): ```typescript function factorialTail(n: number, accumulator: number = 1): number { if (n <= 1) return accumulator; return factorialTail(n - 1, n * accumulator); // nothing happens after this call } console.log(factorialTail(5)); // 120 ``` ### Why Does It Matter? In theory, a tail-recursive function can be optimized by the compiler/runtime into a loop, reusing the same stack frame instead of creating new ones. This is called **tail call optimization (TCO)**. It means you get the elegance of recursion with the memory efficiency of iteration. ### The JavaScript/TypeScript Reality Here's the catch: **most JavaScript engines do not implement TCO**. The ECMAScript 2015 spec technically requires it, but in practice: - **Safari**: supports TCO ✅ - **Chrome/V8**: does not support TCO ❌ - **Firefox**: does not support TCO ❌ - **Node.js**: does not support TCO ❌ So while writing tail-recursive functions is good practice and shows clean thinking, you can't rely on TCO in JavaScript/TypeScript to save you from stack overflows. If stack depth is a concern, convert to iteration. ### Tail Recursive Example: Sum ```typescript function sumTail(n: number, acc: number = 0): number { if (n <= 0) return acc; return sumTail(n - 1, acc + n); } console.log(sumTail(100)); // 5050 console.log(sumTail(10000)); // 50005000 ``` The **accumulator pattern** is the key technique: instead of building up the answer as the stack unwinds, you carry the answer forward as a parameter. > Tail recursion is a useful concept to understand, and the accumulator pattern appears everywhere. But in JavaScript/TypeScript, don't count on the engine to optimize it, convert to a loop if depth is a concern. --- ## Intermediate Problems Now let's tackle problems that push beyond the basics. These require you to think more carefully about what "smaller" means and how to build up complex results. --- ### 1. Flatten a Nested Array Given an array that may contain other arrays nested to any depth, return a single flat array of all values. ```typescript function flatten(arr: unknown[]): unknown[] { const result: unknown[] = []; for (const item of arr) { if (Array.isArray(item)) { result.push(...flatten(item)); } else { result.push(item); } } return result; } console.log(flatten([1, [2, [3, [4]], 5]])); // [1, 2, 3, 4, 5] console.log(flatten([[1, 2], [3, [4, [5, [6]]]]])); // [1, 2, 3, 4, 5, 6] console.log(flatten([[], [1], [[2]], [[[3]]]])); // [1, 2, 3] ``` **How it works:** - Loop through each item in the array. - If the item is an array, recursively flatten it and spread the results into the output. - If the item is not an array, just push it directly. - The recursion handles arbitrary nesting depth because each nested array triggers another round of flattening. **Why recursion is perfect here:** The nesting depth is unknown. You can't write a fixed number of loops. Recursion naturally handles "I don't know how deep this goes" because each call handles one level and delegates deeper levels to the next call. **Complexity:** - Time: **O(n)** where n is the total number of elements across all nesting levels. - Space: **O(d)** for the call stack where d is the maximum nesting depth, plus O(n) for the result array. --- ### 2. Power Set (All Subsets) Given an array of distinct elements, return all possible subsets (the power set). This is a classic problem that introduces you to **recursive choice-making**, the foundation of backtracking. ```typescript function powerSet(arr: number[]): number[][] { const result: number[][] = []; function generate(index: number, current: number[]): void { if (index === arr.length) { result.push([...current]); return; } // Choice 1: include the current element current.push(arr[index]); generate(index + 1, current); current.pop(); // Choice 2: exclude the current element generate(index + 1, current); } generate(0, []); return result; } console.log(powerSet([1, 2, 3])); // [ // [1, 2, 3], [1, 2], [1, 3], [1], // [2, 3], [2], [3], [] // ] ``` **How it works:** At each element, you have two choices: **include it** or **skip it**. The function makes both choices and recurses. When you've considered every element (index reaches the end), you record the current subset. **Visualizing the decision tree for `[1, 2]`:** ``` [] / \ [1] [] / \ / \ [1,2] [1] [2] [] ``` Each leaf is a subset. The tree branches at every element, creating 2ⁿ subsets total. **The include/exclude pattern** is fundamental. It appears in: - Generating combinations - Knapsack problems - Subset sum - Any problem where you make binary choices at each step **Complexity:** - Time: **O(n × 2ⁿ)** — 2ⁿ subsets, each up to length n to copy. - Space: **O(n)** for the call stack depth (plus O(n × 2ⁿ) for storing results). --- ### 3. Palindrome Check (Recursive) You've probably done this iteratively with two pointers. Here's the recursive version, which reveals how recursion mirrors the "shrinking problem" idea. ```typescript function isPalindrome(str: string): boolean { if (str.length <= 1) return true; if (str[0] !== str[str.length - 1]) return false; return isPalindrome(str.slice(1, -1)); } console.log(isPalindrome("racecar")); // true console.log(isPalindrome("hello")); // false console.log(isPalindrome("a")); // true console.log(isPalindrome("abba")); // true console.log(isPalindrome("")); // true ``` **How it works:** - **Base case**: string is empty or one character → it's a palindrome. - **Check**: if the first and last characters don't match → not a palindrome. - **Recursive case**: strip the first and last characters and check the rest. **Trace for `isPalindrome("racecar")`:** ``` isPalindrome("racecar") → 'r' === 'r' ✅ → isPalindrome("aceca") isPalindrome("aceca") → 'a' === 'a' ✅ → isPalindrome("cec") isPalindrome("cec") → 'c' === 'c' ✅ → isPalindrome("e") isPalindrome("e") → true ← base case returns true returns true returns true ``` The string shrinks by 2 characters each call. Like peeling an onion from both ends. **Complexity:** - Time: **O(n)** — at most n/2 recursive calls, but `slice` is O(n) so effectively O(n²). Use index-based version for O(n). - Space: **O(n)** — call stack depth. **Index-based version (optimal):** ```typescript function isPalindromeOpt( str: string, left: number = 0, right: number = str.length - 1 ): boolean { if (left >= right) return true; if (str[left] !== str[right]) return false; return isPalindromeOpt(str, left + 1, right - 1); } ``` --- ### 4. Deep Object Comparison Real-world bonus: recursion is how you deeply compare nested objects. ```typescript function deepEqual(a: unknown, b: unknown): boolean { if (a === b) return true; if ( typeof a !== "object" || typeof b !== "object" || a === null || b === null ) { return false; } const keysA = Object.keys(a as Record); const keysB = Object.keys(b as Record); if (keysA.length !== keysB.length) return false; for (const key of keysA) { if ( !keysB.includes(key) || !deepEqual( (a as Record)[key], (b as Record)[key] ) ) { return false; } } return true; } console.log(deepEqual({ a: { b: 1 } }, { a: { b: 1 } })); // true console.log(deepEqual({ a: { b: 1 } }, { a: { b: 2 } })); // false console.log(deepEqual([1, [2, 3]], [1, [2, 3]])); // true ``` Recursion handles the unknown nesting depth naturally. Each nested object/array triggers a deeper comparison. **Complexity:** - Time: **O(n)** where n is the total number of primitive values across all levels. - Space: **O(d)** where d is the maximum nesting depth. --- ## Recursion on Data Structures Recursion really shines when you're working with **inherently recursive data structures**, structures that are defined in terms of themselves. Trees and linked lists are the classic examples. This section gives you a preview. We'll cover trees and graphs in dedicated articles, but you should see how naturally recursion fits these problems. --- ### Reverse a Linked List (Recursively) ```typescript interface ListNode { val: number; next: ListNode | null; } function reverseList(head: ListNode | null): ListNode | null { if (head === null || head.next === null) return head; const newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; } ``` **How it works:** - **Base case**: the list is empty or has one node → it's already reversed. - **Recursive case**: reverse everything after the current node, then make the next node point back to the current node. **Visualizing `reverseList(1 → 2 → 3 → null)`:** ``` Step 1: reverseList(1 → 2 → 3) Step 2: reverseList(2 → 3) Step 3: reverseList(3) → returns 3 (base case) Now: make 3 point to 2: 3 → 2, and 2 → null Returns: 3 → 2 Now: make 2 point to 1: 3 → 2 → 1, and 1 → null Returns: 3 → 2 → 1 Result: 3 → 2 → 1 → null ``` **Complexity:** - Time: **O(n)** — visit each node once. - Space: **O(n)** — call stack depth equals the list length. --- ### Tree Depth (Maximum Depth of a Binary Tree) This is LeetCode #104, and it's one of the cleanest recursive solutions you'll ever see. ```typescript interface TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; } function maxDepth(root: TreeNode | null): number { if (root === null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); } ``` That's it. Three lines of logic. Recursion makes this almost trivially simple. - **Base case**: null node → depth is 0. - **Recursive case**: the depth is 1 (for the current node) plus the maximum depth of the left or right subtree. **For a tree like:** ``` 1 / \ 2 3 / 4 ``` ``` maxDepth(1) → 1 + max(maxDepth(2), maxDepth(3)) → 1 + max( 1 + max(maxDepth(4), maxDepth(null)), 1 + max(maxDepth(null), maxDepth(null)) ) → 1 + max(1 + max(1, 0), 1 + max(0, 0)) → 1 + max(2, 1) → 3 ``` **Complexity:** - Time: **O(n)** — visit every node once. - Space: **O(h)** — where h is the height of the tree (O(n) worst case for a skewed tree, O(log n) for a balanced tree). > Trees are *defined* recursively: a tree is a node with subtrees. That's why recursive solutions on trees feel so natural, you're matching the structure of the data. ### What's Coming Next These data structure problems deserve their own deep dives, and they're coming: - **Trees: DFS, BFS, and Traversals** - **Graphs: Connected Components, Cycle Detection** - **Backtracking: Permutations, N-Queens, Sudoku** Each of those builds directly on the recursive foundation you're building right now. --- ## Common Pitfalls and Debugging Recursion bugs can be sneaky. The function looks right, the logic seems sound, but something's off. Here are the most common traps and how to avoid them. --- ### 1. Missing Base Case ```typescript // BUG: no base case function countDown(n: number): void { console.log(n); countDown(n - 1); // runs forever → stack overflow } ``` **Fix:** Always define the stopping condition first. ```typescript function countDown(n: number): void { if (n < 0) return; // base case console.log(n); countDown(n - 1); } ``` --- ### 2. Wrong Base Case Sometimes the base case exists but handles the wrong condition. ```typescript // BUG: base case should be n <= 1, not n === 0 function factorial(n: number): number { if (n === 0) return 1; return n * factorial(n - 1); } factorial(-1); // infinite recursion because -1 never hits 0 ``` **Fix:** Use defensive base cases that cover edge inputs. ```typescript function factorial(n: number): number { if (n <= 1) return 1; // handles 0, 1, and negative numbers return n * factorial(n - 1); } ``` > Always ask: "Could my input ever *skip past* the base case?" If calling with `-1` causes `n` to go `-1, -2, -3, ...` and your base case is `n === 0`, you'll never hit it. --- ### 3. Not Reducing the Problem The recursive call must make progress toward the base case. If the input doesn't change (or changes in the wrong direction), you get infinite recursion. ```typescript // BUG: calling with the same input function search(arr: number[], target: number): boolean { if (arr.length === 0) return false; if (arr[0] === target) return true; return search(arr, target); // oops — same array, forever } ``` **Fix:** Make sure the input actually shrinks. ```typescript function search(arr: number[], target: number): boolean { if (arr.length === 0) return false; if (arr[0] === target) return true; return search(arr.slice(1), target); // shrinks the array } ``` --- ### 4. Mutating Shared State This is a subtle one that bites people in backtracking problems. ```typescript // BUG: shared array mutation function subsets(nums: number[]): number[][] { const result: number[][] = []; function helper(index: number, current: number[]): void { if (index === nums.length) { result.push(current); // stores a REFERENCE, not a copy! return; } current.push(nums[index]); helper(index + 1, current); current.pop(); helper(index + 1, current); } helper(0, []); return result; // every entry is the same empty array } ``` **Fix:** Copy the array when storing it. ```typescript result.push([...current]); // spread to create a new copy ``` When you push a reference to `current`, every entry in `result` points to the same array. As `current` gets mutated by `push` and `pop`, all stored references reflect the final state (empty). Spreading creates an independent snapshot. --- ### 5. Forgetting to Return In recursive functions that compute a value, every code path must return something. Forgetting the `return` before a recursive call is a classic mistake. ```typescript // BUG: missing return function sum(n: number): number { if (n <= 0) return 0; sum(n - 1); // calls recursively but doesn't return the result! } console.log(sum(5)); // undefined ``` **Fix:** Always return the recursive result. ```typescript function sum(n: number): number { if (n <= 0) return 0; return n + sum(n - 1); } ``` > Debugging tip: when a recursive function returns `undefined` or `NaN`, check that every path has a `return` statement. It's almost always a missing `return`. --- ### Debugging Strategy When your recursive function isn't working: 1. **Add logging.** Print the input at the start of each call: `console.log("called with:", input)`. This shows you the call sequence and whether inputs are shrinking. 2. **Trace by hand.** Pick a small input (n=3, array of 2 elements) and trace every call on paper. Most bugs become obvious with small inputs. 3. **Check the base case.** Is it correct? Does it handle all edge cases? Can the input skip past it? 4. **Check the recursive call.** Is the input actually getting smaller? Are you returning the result? 5. **Check state mutation.** Are you accidentally sharing or mutating data between calls? --- ## Pattern Recognition: When to Think Recursively Not every problem should be solved with recursion. But some problems are *screaming* for it. Here's how to recognize them. --- ### Signal 1: The Problem Has Subproblem Structure If solving the big problem requires solving smaller versions of the exact same problem, that's recursion. - "Find the sum of all elements" → sum of first element + sum of the rest - "Find the maximum depth" → 1 + max of depth of children - "Is this a palindrome?" → check ends + is the middle a palindrome? > If you can describe the solution as "solve the same problem on a smaller input," it's recursive. --- ### Signal 2: The Data Is Nested or Hierarchical Trees, graphs, nested objects, nested arrays, file systems, org charts, these are all recursive structures. The data itself is defined in terms of smaller instances of itself. - A tree node has child tree nodes - A directory contains files and subdirectories - A JSON object can contain other JSON objects When the data is recursive, the solution should probably be too. --- ### Signal 3: You Need to Explore All Possibilities Problems that ask for "all combinations," "all permutations," "all paths," or "all subsets" are almost always recursive. You make a choice, recurse, then backtrack and make a different choice. - Generate all subsets - Find all paths in a maze - Solve N-Queens - Generate valid parentheses --- ### Signal 4: Divide and Conquer If you can split the problem in half, solve each half, and combine the results, that's recursive. - Merge sort: split, sort halves, merge - Quick sort: partition, sort halves - Binary search (recursive version) - Fast exponentiation (we saw this earlier) --- ### Signal 5: The Problem Says "Recursive" in Disguise Some problem descriptions use keywords that hint at recursion without saying it: | Keyword / Phrase | Likely Pattern | |---|---| | "All subsets" or "all combinations" | Backtracking (recursion + choices) | | "Nested" or "depth" | Recursive traversal | | "Tree" or "graph" | DFS/BFS (often recursive DFS) | | "Divide and conquer" | Split + recurse + combine | | "Optimal substructure" | Dynamic programming (recursion + memoization) | | "Can you do it recursively?" | ...recursion | --- ### When NOT to Use Recursion Not everything deserves recursion. Avoid it when: - A simple loop does the job clearly (iterating through an array to find a max) - The recursion depth could be enormous (millions of elements in a flat list) - There's no natural subproblem structure (the problem doesn't break into smaller versions of itself) - You're overcomplicating a fundamentally iterative process > Recursion is a tool, not a personality. Use it when it makes the solution clearer, simpler, or when the problem structure demands it. Otherwise, a loop is perfectly fine. --- ## Cheat Sheet / Quick Reference ### The Recursive Function Template ```typescript function solve(input: T): R { // 1. Base case if (isBaseCase(input)) return baseResult; // 2. Recursive case: break down + combine return combine(process(input), solve(smaller(input))); } ``` ### Common Base Cases | Data Type | Typical Base Case | |---|---| | Number | `n <= 0` or `n === 1` | | String | `str.length <= 1` or `str === ""` | | Array | `arr.length === 0` | | Linked List | `node === null` | | Tree Node | `node === null` | | Index | `index >= arr.length` or `index < 0` | ### Common Recursive Patterns | Pattern | Structure | Example Problems | |---|---|---| | **Linear recursion** | `f(n) = work + f(n-1)` | Factorial, sum, reverse | | **Binary recursion** | `f(n) = f(n-1) + f(n-2)` | Fibonacci, tree traversals | | **Divide and conquer** | `f(n) = combine(f(left), f(right))` | Merge sort, max depth | | **Backtracking** | Make choice → recurse → undo choice | Subsets, permutations, N-Queens | | **Accumulator** | `f(n, acc)` — carry result forward | Tail-recursive sum, factorial | ### Big O Quick Reference | Problem | Time | Space | |---|---|---| | Factorial | O(n) | O(n) | | Fibonacci (naive) | O(2ⁿ) | O(n) | | Fibonacci (memoized) | O(n) | O(n) | | Sum of array | O(n) | O(n) | | Reverse string | O(n²)* | O(n) | | Fast exponentiation | O(log n) | O(log n) | | Power set | O(n × 2ⁿ) | O(n) | | Flatten nested array | O(n) | O(d) | | Tree max depth | O(n) | O(h) | | Reverse linked list | O(n) | O(n) | *String concatenation cost; O(n) with array-based approach. ### Debugging Checklist - [ ] Does every base case return a value? - [ ] Does the input actually shrink toward the base case? - [ ] Can the input ever skip past the base case? - [ ] Am I returning the recursive call's result? - [ ] Am I mutating shared state? (Copy arrays/objects when storing) - [ ] Is the recursion depth safe? (No stack overflow risk?) --- ## What's Next You now have a solid foundation in recursive thinking. You understand the call stack, you can write base cases and recursive cases, you've solved real problems, and you know when to reach for recursion vs iteration. But this is just the beginning. Recursion is the *prerequisite* for some of the most important topics in computer science and interview prep: - **Depth-First Search (DFS) and Breadth-First Search (BFS)** — Recursion is how you traverse trees and graphs. DFS is literally recursion on a graph. - **Backtracking** — The power set problem above was your first taste. Backtracking extends this to permutations, N-Queens, Sudoku solvers, and constraint satisfaction problems. - **Dynamic Programming** — Remember memoized Fibonacci? That's the core idea behind DP. You identify overlapping subproblems, cache results, and turn exponential solutions into polynomial ones. - **Divide and Conquer** — Merge sort, quick sort, and many optimization problems split the input, solve recursively, and combine. You've already seen this with fast exponentiation. - **Tree and Graph Algorithms** — Traversals, path finding, lowest common ancestor, serialization — almost all of these are recursive at their core. Each of these topics gets its own "Made Simple" article. The patterns stack on each other, and recursion is the layer they all sit on. > "Recursion is not just a technique. It's a way of seeing problems — as smaller versions of themselves, all the way down." Keep practicing. Pick a problem, identify the base case and the recursive case, and write it out. The more you do it, the more natural it becomes. And one day, you'll look at a complex tree problem and think, "Oh, that's just recursion," and you'll smile, because it finally clicked. --- ## Thanks for Reading! If this helped you, share it with a friend who's struggling with recursion. The best way to solidify your understanding is to explain it to someone else, and hey, that's kind of recursive too. Keep building. Keep solving. You've got this. **Your Dev Brain, Now Thinking Recursively** ---

Problem Solving Patterns: Recursion, Made Simple