Recursion

Recursion is the moment programming starts to feel like magic. A function calls itself, the call stack does the bookkeeping, and a problem you couldn't even write a loop for falls out in three lines. The catch: every recursive call costs a stack frame, and "thinking recursively" is a different skill from "thinking iteratively". You have to trust the recursion — assume the recursive call works, and just handle the *one* step you're standing on.

What Recursion Actually Is

A recursive function is a function defined in terms of *itself on a smaller input*. Two ingredients are non-negotiable:

1. Base case — the simplest input that you can answer directly, without recursing. This stops the chain. 2. Recursive case — break the problem into a smaller version of itself, call yourself on it, then build the answer.

A third invisible ingredient: progress. Each recursive call must move *strictly closer* to the base case. Without that, you've written infinite recursion → stack overflow.

\\\`js function factorial(n) { if (n <= 1) return 1; // base case return n * factorial(n - 1); // recursive case (smaller n) } \\\`

The Daily Mental Model: "Trust the Recursion"

The most useful trick when learning recursion: don't try to trace it in your head. Instead:

1. Write the base case first. 2. For the recursive case, *assume* the function already works for smaller inputs. 3. Use that assumed-working call to build the answer for the current input.

For \factorial(n)\: assume \factorial(n-1)\ returns \(n-1)!\ correctly. Then \n * factorial(n-1)\ is obviously \n!\. Done. Don't trace what \factorial(3)\ does step by step — it's a waste of time and your stack will overflow before your patience does.

How the Call Stack Works

Each call gets a stack frame holding its parameters, local variables, and the return address. Frames pile up while we recurse *down*, then unwind one by one as the base case starts returning.

\\\` factorial(4) called [factorial(4)] factorial(3) called [factorial(4), factorial(3)] factorial(2) called [factorial(4), factorial(3), factorial(2)] factorial(1) → 1 [factorial(4), factorial(3), factorial(2)] ← unwind factorial(2) → 2 * 1 [factorial(4), factorial(3)] factorial(3) → 3 * 2 [factorial(4)] factorial(4) → 4 * 6 = 24 [] \\\`

Each frame uses memory. n recursive calls = O(n) stack space, even if you didn't allocate anything yourself. That's why \factorial(100000)\ will overflow in JavaScript while a loop won't.

Beginner Mistakes to Skip

1. No base case → infinite recursion → stack overflow. Always write the base case *first*. 2. Base case is unreachable. \if (n === 0) return 0;\ but you call \factorial(-1)\ — n decrements past 0 forever. Use \n <= 0\ or validate inputs. 3. Forgetting to \return\ the recursive call. \factorial(n - 1) * n\ → does nothing if you don't return it. Surprisingly common. 4. Recursing on the same input. \factorial(n)\ instead of \factorial(n - 1)\ — no progress, infinite recursion. 5. Tracing recursion by hand for n = 20. You will run out of paper. Trust the recursion. Verify on \n = 0, 1, 2, 3\ only. 6. Treating tail recursion like iteration in JS. JavaScript engines mostly don't optimise tail calls, so deep tail-recursive code still overflows. Convert to a loop.

Intermediate: Head vs Tail Recursion

Head (or "regular") recursion — the function does work *after* the recursive call returns:

\\\`js function sumDown(n) { if (n === 0) return 0; return n + sumDown(n - 1); // ← addition happens AFTER the call returns } \\\`

Tail recursion — the recursive call is the *very last* thing the function does. No work pending after it returns:

\\\`js function sumDownTail(n, acc = 0) { if (n === 0) return acc; return sumDownTail(n - 1, acc + n); // ← the call IS the return value } \\\`

Why does anyone care? A compiler that supports Tail Call Optimization (TCO) can reuse the *same* stack frame for the recursive call — turning recursion into a loop with O(1) space. Scheme, Haskell, and Scala do this. JavaScript is in the spec but engines don't implement it. Java doesn't. Python deliberately doesn't.

So: tail recursion is a beautiful idea, but in mainstream languages you still get stack overflow on deep recursion. Convert to a loop manually.

Intermediate: Recursion vs Iteration

Aspect	Recursion	Iteration
Approach	Top-down (split, then combine)	Bottom-up (build up)
Memory	O(depth) stack frames	O(1) usually
Code clarity	Wins on trees, graphs, divide-and-conquer	Wins on simple linear loops
Speed	Function-call overhead	Usually faster
Stack-overflow risk	Yes	No

Conversion principle: Any recursion can be converted to iteration using an explicit stack that mimics the call stack:

\\\`js // Recursive in-order traversal function inorder(node) { if (!node) return; inorder(node.left); visit(node); inorder(node.right); }

// Iterative with an explicit stack function inorderIter(root) { const stack = []; let node = root; while (node || stack.length) { while (node) { stack.push(node); node = node.left; } node = stack.pop(); visit(node); node = node.right; } } \\\`

Intermediate: The Three Big Recursive Patterns

1. Divide and Conquer — split the problem in roughly equal halves, solve each recursively, *combine*.

• Merge sort, quicksort, binary search, FFT, closest-pair-of-points.
• Recurrence usually \T(n) = 2 T(n/2) + O(n)\ → O(n log n).

2. Backtracking — try a choice, recurse; if it fails, *undo* the choice and try the next one.

• N-Queens, sudoku solver, generating permutations / subsets / combinations, maze solving.

\\\` function backtrack(state): if isSolution(state): record(state); return for choice in choices: if isValid(choice): apply(choice) // do backtrack(state) // recurse undo(choice) // undo \\\`

3. Tree recursion — multiple recursive calls per invocation (branching). Creates a *recursion tree*.

• Naive Fibonacci (\fib(n) = fib(n-1) + fib(n-2)\), tree traversals, generating subsets.
• Without memoisation, often exponential.

Advanced: Memoisation — From O(2ⁿ) to O(n)

Naive Fibonacci recomputes the same subproblems thousands of times:

\\\` fib(5) → fib(4) + fib(3) → (fib(3) + fib(2)) + (fib(2) + fib(1)) ← fib(3), fib(2) recomputed \\\`

Memoise — cache the answer the first time you compute it:

\\\`js const memo = new Map(); function fib(n) { if (n < 2) return n; if (memo.has(n)) return memo.get(n); const result = fib(n - 1) + fib(n - 2); memo.set(n, result); return result; } \\\`

• Naive: O(2ⁿ) time, O(n) space.
• Memoised: O(n) time, O(n) space.
• This is the bridge from recursion to dynamic programming — top-down DP is just memoised recursion.

Advanced: Recursion-Tree Analysis

To find the time complexity of a recursive function, draw the recursion tree and sum the work across all nodes.

Merge sort: \T(n) = 2 T(n/2) + O(n)\

\\\` Level 0: 1 problem of size n → O(n) merge work Level 1: 2 problems of size n/2 → 2 * O(n/2) = O(n) total Level 2: 4 problems of size n/4 → O(n) total … Level log n: n problems of size 1 → O(n) total \\\`

Each level costs O(n). There are O(log n) levels. Total: O(n log n).

Master Theorem (\T(n) = a T(n/b) + O(n^d)\) gives the answer in one line if the recurrence fits the pattern.

Advanced: Stack Overflow — Causes and Defences

Each call uses ~100 bytes of stack. The default stack is ~1 MB → roughly 10,000 frames before the JS engine crashes (varies by engine and frame size). For Python it's hard-capped at 1000 by default; raise it with \sys.setrecursionlimit\.

Defences:

1. Convert to iteration with an explicit stack — most reliable. 2. Memoise — a memoised recursive function makes far fewer calls. 3. Trampolining — return a *thunk* (function) instead of recursing directly, then loop:

\\\`js function trampoline(fn) { let result = fn(); while (typeof result === 'function') result = result(); return result; } function sumThunked(n, acc = 0) { if (n === 0) return acc; return () => sumThunked(n - 1, acc + n); // returns a thunk } trampoline(() => sumThunked(1000000)); // works without overflow \\\`

4. Tail recursion — only helps in languages that actually do TCO. 5. Increase the stack (\ulimit -s\ on Unix, \-Xss\ on the JVM) — last resort.

Advanced: Classic Problems Cheatsheet

Problem	Pattern	Time
Factorial	Linear	O(n)
Fibonacci (memoised)	Tree → memo	O(n)
Tower of Hanoi	Tree	O(2ⁿ)
Permutations of n	Backtracking	O(n · n!)
All subsets	Backtracking	O(n · 2ⁿ)
Merge sort / quicksort	Divide & conquer	O(n log n)
Binary search	Divide & conquer	O(log n)
Tree traversals	Single recursion	O(n)
N-Queens	Backtracking	O(n!)

Practice Path

1. Write \factorial(n)\ and \sum(n)\ recursively. Then rewrite both as loops. Notice the loops have an explicit accumulator. 2. Implement \fib(n)\ naively, then add memoisation. Time both for n = 35 — the difference will be dramatic. 3. Generate all subsets of \[1, 2, 3]\ using "include or exclude each element". Then generate all permutations using backtracking. 4. Convert in-order tree traversal from recursive to iterative using an explicit stack.