This is a standalone course on recursion — built to take you from "I freeze on recursion" to writing it cold in FAANG / SDE2–SDE3 interviews. It assumes nothing from any other sheet; everything you need is here. The core belief: recursion feels hard only because people try to trace it — following every call in their head until they're dizzy. Strong engineers never trace. They define a contract and trust it (the Leap of Faith, §1), then verify just one level. Before you write a single line, name WHICH of the 5 archetypes (§2) the problem is — that one classification decision does more for you in an interview than any amount of tracing. Return values are the thing you said trips you up, so they get the most attention: §3's live derivations, the two ⭐ sections §5–§6, and the diagrams in §11 and §14.

HOW TO USE THIS DOCUMENT — a learning path (don't just skim top→bottom)
──────────────────────────────────────────────────────────────────────
  PHASE 1 · UNDERSTAND   §1–§8    the mindset, the 5 archetypes, the 4
                                  questions, and the two ⭐ return-value
                                  sections. Read slowly, ONCE, with a pen.
                                  Do the live derivations in §3.

  PHASE 2 · PATTERNS     §9–§15   the handful of shapes every recursive
                                  solution takes. Try to write each one
                                  yourself BEFORE reading the code.

  PHASE 3 · APPLY TO DSA §16–§17  how recursion BECOMES dp, backtracking,
                          + §20   divide & conquer, and tree/graph search —
                                  the actual interview topics.

  PHASE 4 · DRILL        §18–§19  bug patterns, the keyword→approach map,
                          + §21   and the LC coverage table — then the
                                  self-test (active recall) to prove it.

  GOLDEN HABIT: cover the code, predict the base case + the combine line,
  THEN look. Recursion is learned by producing it, not by reading it.

1. THE RECURSION MINDSET

🔑 The one idea that unlocks everything — the Leap of Faith: Assume your function already works for any smaller input. Don't look inside it. Your only job is to handle one level: turn the answer for the smaller input into the answer for the current input.

WHAT RECURSION ACTUALLY IS
──────────────────────────────────────────────────────────
Solve a problem by solving a SMALLER version of the SAME
problem, then doing a tiny bit of work to combine.

You write ONE level. The machine repeats it for you.

THE LINE ANALOGY (burn this into memory)
You are standing in a line and want your position.
  • You DON'T count everyone (that's iteration / tracing).
  • You tap the person in front: "what's your number?"
  • You trust their answer X, and reply  X + 1.
  • The FIRST person has nobody ahead → answers "1".  (BASE CASE)
That is recursion: trust the smaller answer, add your bit.

THREE MENTAL MOVES
  1. Shrink   — make the input smaller (n-1, n/2, node.left)
  2. Trust    — assume the recursive call returns the right thing
  3. Combine  — do O(1)-ish work to build your answer from it

⚠️ Stop tracing. If you ever find yourself drawing the 4th level of a call tree to "see if it works," you've left the recursive mindset. Verify only two things: (a) the base case is correct, and (b) one recursive step is correct assuming the call below it is correct. Induction does the rest — for free.

2. ⭐ THE 5 ARCHETYPES OF RECURSION — name the conversation before you code

🔑 The move that separates senior engineers from someone who's memorized templates: before you touch the 4-question framework (§3) or pick a shape (§9), ask "which of these 5 conversations is my function having with its children?" That single classification decision is why a senior engineer stares at a new problem for 20 seconds and then just writes it, while everyone else starts typing and gets lost halfway through. It's the missing layer above "how do I write the code" — it's "what KIND of thing am I even building."

THE QUESTION BEHIND THE QUESTION: "who ends up holding the final answer,
and how did it get there?" Five different answers, five archetypes:

  1. BUBBLE-UP        "Child, what's YOUR answer?" I trust it, I combine
     (return-value)    it with my bit, I hand MY answer up to MY parent.

  2. CARRY-DOWN        "Here's what you need to know." I hand context
     (state-passing)   DOWN so my children don't have to re-derive it.

  3. GLOBAL-ANSWER     "Everyone write to the same whiteboard." No single
     (shared/closure)  return value holds the final answer — every frame
                        just might update one shared slot as it passes by.

  4. EXPLORE-ALL       "Try every choice, then take it back." Loop over
     (backtracking)    every option, recurse, undo — build the full
                        search space instead of one answer.

  5. REMEMBER          "Have I already answered THIS exact question?"
     (memo → DP)        Same recursion as #1, plus a cache, because the
                        same sub-question keeps getting asked.

#1 vs #2 — you already know these; they're §5's Style A / Style B, just renamed as "conversations" instead of "styles." The new, higher-leverage ideas here are #3, #4, and #5 — worked below.

⚠️ The trap that fools people who think they understand bubble-up: this function DOES have a return statement, so it LOOKS like archetype 1. But look at what's returned: it's the height, not the diameter. The diameter — the actual answer to the problem — is never returned by anyone. It's written to a shared variable that every frame is allowed to update as it passes through.

function diameterOfBinaryTree(root: TreeNode | null): number {
  let best = 0;                                    // the SHARED WHITEBOARD — the real answer lives here
  function height(node: TreeNode | null): number {  // this still returns something — but NOT the final answer
    if (node === null) return 0;
    const L = height(node.left);
    const R = height(node.right);
    best = Math.max(best, L + R);                  // side-channel write: "the best path THROUGH me"
    return 1 + Math.max(L, R);                      // plumbing: what MY PARENT needs to keep computing heights
  }
  height(root);
  return best;                                       // the real answer, read back out at the end
}

🔑 Why you need this archetype at all: the winning path can be centered at ANY node, not just the root. A pure bubble-up return can only tell you "the best answer within my subtree" — that's a different question than "the best answer seen anywhere so far." Rather than thread a second value through every single return in the tree, you park it in one shared slot everyone can touch. Nuance for the interview: this is a CHOICE, not a law of physics — you could instead return a [height, bestSoFar] tuple and bubble both up (pure archetype 1). Global-answer is simply less bookkeeping. Naming both options out loud is a senior move.

The tell: the problem doesn't want ONE answer, it wants EVERY answer. That forces a different contract: instead of "return the answer," it's "for each choice, recurse into it, then undo the choice so my sibling starts clean." Full mechanics, pruning, and 10+ templates live in backtracking.html — this is just the recursive skeleton underneath.

function subsets(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  function dfs(i: number): void {
    if (i === nums.length) { res.push([...path]); return; }  // base: record ONE complete answer
    path.push(nums[i]); dfs(i + 1); path.pop();                // choice A: take nums[i] … then UNDO
    dfs(i + 1);                                                  // choice B: skip nums[i]
  }
  dfs(0);
  return res;
}

The tell: archetype 1 (bubble-up), but the same (n) or (i, j, remaining) tuple gets asked more than once as the tree unfolds. You don't redesign the recursion — you wrap it with a cache. Full derivation, the recursion tree, and the top-down→bottom-up conversion live in §16.

Same function, ONE line added:
  archetype 1:  return f(n-1) + f(n-2);
  archetype 5:  if (memo.has(n)) return memo.get(n);
                const ans = f(n-1) + f(n-2);
                memo.set(n, ans); return ans;

🔑 The 10-second classifier — run through in order, stop at the first "yes":

Does the same (n) / (i,j) tuple get asked more than once?
   → YES: archetype 5, REMEMBER (memo). Design it as #1 first, then cache.

Does the problem say "all / every / list them / how many WAYS
(as distinct sequences, not just a count)"?
   → YES: archetype 4, EXPLORE-ALL (backtracking).

Can the final answer live ANYWHERE in the tree, not just be
computable from the root's own return value?
   → YES: archetype 3, GLOBAL-ANSWER (closure/shared var).

Does a child need to know something only an ancestor has seen
(an index, a running sum, a path-so-far)?
   → YES: archetype 2, CARRY-DOWN (state-passing).

Otherwise:
   → archetype 1, BUBBLE-UP (return-value). This is the default —
     most problems are this one. Reach for the others only when
     bubble-up alone can't say what you need.

3. THE 4-QUESTION FRAMEWORK

Answer these 4 questions, in order, and the code writes itself. Do them on paper before touching the keyboard. Most "I can't think recursively" moments are really "I skipped Q0".

Q0. CONTRACT  — "What does f(x) return / do, in ONE sentence?"
    Write it as a precise English sentence FIRST. Everything
    else is derived from this. If you can't say it, you can't
    code it.
      e.g. "height(node) = number of nodes on the longest
            path from node down to a leaf."

Q1. BASE CASE — "What is the smallest input I can answer
    WITHOUT recursing?" Return that answer directly.
      e.g. height(null) = 0.

Q2. RECURSIVE CASE (the leap) — "If f already works for the
    smaller input, how do I build f(x) from it?"
      e.g. height(node) = 1 + max(height(left), height(right)).

Q3. PROGRESS — "Does every call move strictly toward the
    base case?" (smaller n, smaller subtree, higher index…)
    If not → infinite recursion / stack overflow.

// The 4 questions, mapped onto code, for height-of-tree:
class TreeNode { val = 0; left: TreeNode | null = null; right: TreeNode | null = null; }

function height(node: TreeNode | null): number {   // Q0: returns # nodes on longest root→leaf path
  if (node === null) return 0;                      // Q1: base case, answered directly
  const L = height(node.left);                      // Q2: TRUST these return correct heights
  const R = height(node.right);                     //     (the leap of faith — don't trace in)
  return 1 + Math.max(L, R);                        // Q2: combine into MY answer
  // Q3: node.left / node.right are strictly smaller → progress guaranteed
}

Why this order matters. Q0 fixes the meaning and the return type. Q1 gives you the value to start from. Q2 is the only "creative" step, and it's easy once Q0 is precise. Q3 is your safety check. Beginners jump straight to Q2 and flail; seniors spend 80% of their time on Q0.

▶ Apply the framework LIVE — derive three from scratch

🔑 This is the most important part of the document for you. Watch the 4 questions turn a blank screen into working code. Cover the code block and try it yourself first — predict the base case and the combine line, then look. Notice the rhythm repeats every single time.

DERIVATION 1 — sum of an array          (shape: LINEAR, 1 call)
  Q0 CONTRACT : sum(a, i) returns the sum of a[i], a[i+1], …, last.
  Q1 BY HAND  : sum of nothing (i past the end) = 0.
                sum([7], i=0) = 7 + (sum of nothing) = 7. ✓
                → base case = "i reached the end" → return 0.
  Q2 LEAP     : TRUST sum(a, i+1) = "sum of the rest". Then
                sum(a, i) = a[i] + sum(a, i+1).
  Q3 PROGRESS : i grows by 1 each call → always reaches a.length. ✓

function sum(a: number[], i = 0): number {
  if (i === a.length) return 0;       // Q1 — base case
  return a[i] + sum(a, i + 1);        // Q2 — my element + trusted sum of the rest
}

DERIVATION 2 — height of a binary tree   (shape: TREE, 2 calls)
  Q0 CONTRACT : depth(node) returns the # of nodes on the longest
                path from node down to a leaf.
  Q1 BY HAND  : depth(null) = 0 (no nodes).
                depth(one leaf) = 1 + max(0, 0) = 1. ✓
                → base case = "node is null" → return 0.
  Q2 LEAP     : TRUST depth(left) and depth(right). Then
                depth(node) = 1 + max(depth(left), depth(right)).
  Q3 PROGRESS : each child is a strictly smaller subtree → hits null. ✓

function depth(node: TreeNode | null): number {
  if (node === null) return 0;                                 // Q1
  return 1 + Math.max(depth(node.left), depth(node.right));    // Q2
}

DERIVATION 3 — climb stairs, 1 or 2 at a time  (shape: BRANCHING → DP)
  Q0 CONTRACT : ways(n) returns the # of distinct ways to climb n steps.
  Q1 BY HAND  : ways(0) = 1 (one way: you're already at the top).
                ways(1) = 1.   ways(2) = ways(1) + ways(0) = 2. ✓
                → base cases = n===0 → 1,  n<0 → 0 (overshot the top).
  Q2 LEAP     : my last move was a 1-step OR a 2-step. TRUST both:
                ways(n) = ways(n-1) + ways(n-2).
  Q3 PROGRESS : n shrinks each call → reaches 0 / negative. ✓
  NOTE        : the same ways(k) is recomputed many times → add a memo
                and this IS the classic DP, LC 70. (see §16)

function ways(n: number): number {
  if (n < 0) return 0;                  // Q1 — overshot
  if (n === 0) return 1;                // Q1 — reached the top
  return ways(n - 1) + ways(n - 2);     // Q2 — sum the two trusted universes
}

See the rhythm? Contract → solve the tiniest cases by hand → the base case falls out of the tiniest case → the combine line is always "(my current element / node / last move) ＋ (the trusted smaller answer)." Every recursion you will ever write in an interview follows this exact rhythm. Drill these three until you can reproduce each in under a minute.

4. UNIVERSAL TEMPLATE

// Memorize this skeleton. Every recursion is a fill-in-the-blanks of it.
function f(input: Input): Output {
  // 1) BASE CASE(S): smallest inputs, answered without recursion
  if (/* smallest case */) return /* known answer */;

  // 2) (optional) PREPARE: shrink the problem / pick the choices

  // 3) RECURSE: call f on STRICTLY SMALLER input(s) — TRUST the result
  const sub = f(/* smaller input */);

  // 4) COMBINE: do O(1)-ish work to turn sub-answer(s) into MY answer
  return /* combine(sub, current-element) */;
}

THE FOUR SLOTS — fill these in and you're done
┌────────────┬──────────────────────────────────────────────┐
│ SLOT       │ QUESTION TO ASK YOURSELF                      │
├────────────┼──────────────────────────────────────────────┤
│ Base case  │ Smallest input? What's its answer?           │
│ Shrink     │ How do I make the input smaller? (n-1, n/2)  │
│ Recurse    │ Call f on the smaller thing. TRUST it.       │
│ Combine    │ child-answer  +  my-one-step-of-work  = ans  │
└────────────┴──────────────────────────────────────────────┘

5. ⭐ RETURN-VALUE vs VOID — THE BIG FORK

This is the thing you said trips you up, so read it twice. There are exactly two ways a recursion can produce an answer. Almost all confusion about "what do I return" comes from mixing them. Pick ONE style per function.

🔑 The load-bearing analogy — a report vs. a relay baton. Style A (bubble-up) is you reporting to your manager: you ask your one direct report a single question, wait for their one-number answer, add your own bit, and hand ONE number to your manager. Nobody above you ever sees anyone else's raw numbers — just yours, already combined. Style B (carry-down) is a relay race: the baton (your running total, your path-so-far) gets handed FORWARD, runner to runner. Nothing meaningful happens on the way back — the race is already decided the moment the last runner crosses the line holding the baton. If you can say which of these two your function is doing, you already know what to return.

// SAME PROBLEM, BOTH STYLES — sum of an array from index i onward.

// STYLE A — BUBBLE UP: the value comes back through `return`.
function sumUp(a: number[], i: number): number {
  if (i === a.length) return 0;            // base: empty tail sums to 0
  return a[i] + sumUp(a, i + 1);           // my element + (trusted) sum of the rest
}

// STYLE B — CARRY DOWN: the running total rides in a parameter (accumulator).
function sumDown(a: number[], i: number, acc: number): number {
  if (i === a.length) return acc;          // base: the answer is whatever we accumulated
  return sumDown(a, i + 1, acc + a[i]);    // add now, pass forward; nothing to combine on the way up
}
// sumUp(a,0) and sumDown(a,0,0) give the same number.
// Notice: in A the work happens AFTER the call (on the way up);
//         in B the work happens BEFORE the call (on the way down).

🔑 The decision in 5 seconds: Can I write the answer as combine(myElement, f(rest))? → Style A (return). Do I instead need to remember the whole path so far to record it at the end? → Style B (carry down + collect). Backtracking is Style B with an undo step — see the Backtracking sheet.

6. ⭐ HOW TO FIGURE OUT THE RETURN VALUE

A repeatable 3-step recipe for "I don't know what to return." Run this every time and you'll never be stuck on a return value again.

🔑 The analogy — you're signing a contract before you do any work. A recruiter won't let you start a job without agreeing what you're being paid to deliver. Step 1 is you writing that one-sentence job description for yourself ("this function's job is to return ___"). Once it's written down, Steps 2 and 3 are just honoring that contract for the easiest case and then the general case — you're not inventing anything new, you're fulfilling a promise you already made in Step 1.

STEP 1 — NAME THE RETURN (write the contract sentence).
   "f(x) returns ______."  Be specific about type AND meaning.
   The type you name here MUST be the same in every branch.
     number? list? boolean? a tree node? a tuple?

STEP 2 — RETURN FOR THE SMALLEST INPUT (base case value).
   Plug the tiniest input into your sentence. What's the answer?
   This pins down the return TYPE and the identity/empty value.
     sum of []      → 0          (additive identity)
     product of []  → 1          (multiplicative identity)
     longest path of null → 0
     "found target in empty list?" → false
     reverse of "" → ""

STEP 3 — RETURN FOR THE GENERAL INPUT (the leap).
   Say out loud: "I have the child's answer. I trust it.
   What ONE operation turns it into MY answer?"
   That sentence IS your recursive return line.
     count(node)   = 1 + count(left) + count(right)
     max(node)     = max(node.val, max(left), max(right))
     exists(x,i)   = a[i]===x || exists(x,i+1)

GOLDEN RULE: base case and recursive case must return the
SAME TYPE. If base returns a number, recursion returns a number.
Type-mismatch between branches = your bug.

The pattern you should now SEE: the base return is always the identity element of whatever operation combines the answers — the value that changes nothing when combined. +'s identity is 0, *'s is 1, ||'s is false, &&'s is true, string concat's is "". Some operations (like max/min) have no identity element at all — for those, stop one step earlier and let the base case be the LAST single element instead of an empty input.

Trick for boolean returns: use || ("does ANY branch succeed?") or && ("do ALL branches succeed?"). Short-circuiting also prunes for free. Trick for "return the node/path itself": the return type is the node/list, base returns null / [], and you reattach the child's returned node — see reverse-linked-list and tree-build problems.

7. FINDING THE BASE CASE

Rule: the base case is the input so small that recursing would make it illegal or trivial. Find it by asking "what's the smallest input my recursive line could be handed?" — then make sure that input never reaches the recursive line.

WHERE BASE CASES LIVE (by input type)
  array / index  → i === arr.length   (ran off the end)   → identity
                 → i > j              (empty window)
                 → low > high         (binary search miss)
  number n       → n === 0  or  n === 1
  string         → s.length === 0  or  start === s.length
  tree node      → node === null      (most common!)
                 → node.left === null && node.right === null  (leaf)
  linked list    → head === null  or  head.next === null
  2D grid        → out of bounds, or cell already visited

TWO BASE-CASE STYLES FOR TREES (know both)
  A) Guard on null:   if (node === null) return 0;
     → simplest, handles empty tree, lets you recurse blindly.
  B) Guard on leaf:   if (!node.left && !node.right) return node.val;
     → needed when "leaf" is special (e.g. root-to-leaf sums).
     → DANGER: must also handle a node with ONE child, or you
       recurse into null and crash. Prefer style A when unsure.

CHECKLIST
  ☑ Does the base case return the SAME TYPE as the recursive case?
  ☑ Is it reachable? (does progress actually shrink toward it?)
  ☑ Did I cover EVERY tiny input? (empty AND single-element)
  ☑ For two-branch recursion, can a child be null/empty?

// Missing/weak base case is the #1 cause of stack overflow.
// BAD: only stops at exactly length → negative or skipped index loops forever
function bad(a: number[], i: number): number {
  if (i === a.length) return 0;
  return bad(a, i + 2);          // if length is odd, i jumps PAST length → never equal → 💥
}
// GOOD: use >= so you can never "overshoot" the base case
function good(a: number[], i: number): number {
  if (i >= a.length) return 0;  // catches i === length AND i === length+1
  return good(a, i + 2);
}

8. THE CALL STACK & ORDER OF WORK

Pre vs Post: code before the recursive call runs on the way DOWN (top→base). Code after it runs on the way UP (base→top). Swapping those two lines is the difference between printing 1→n and n→1. Internalize this and half of "recursion magic" disappears.

function down(n: number): void {   // work BEFORE recurse → executes on the way DOWN
  if (n === 0) return;
  console.log(n);                  // prints n, n-1, ... 1   (5 4 3 2 1)
  down(n - 1);
}
function up(n: number): void {     // work AFTER recurse → executes on the way UP
  if (n === 0) return;
  up(n - 1);
  console.log(n);                  // prints 1, 2, ... n     (1 2 3 4 5)
}

CALL STACK FOR down(3) — frames PUSH going down, POP coming up
  call down(3)  ─┐ print 3
    call down(2) │  print 2
      call down(1)   print 1
        call down(0) base → return
      return ◄──── unwinding (nothing prints in `down`)
    return ◄────
  return ◄────
The stack's MAX HEIGHT = recursion depth = your SPACE cost.

THE THREE TRAVERSAL ORDERS ARE JUST "WHEN DO I VISIT ME?"
  preorder:   visit(me); recurse(L); recurse(R);   // me first (down)
  inorder:    recurse(L); visit(me); recurse(R);   // me in middle (BST→sorted)
  postorder:  recurse(L); recurse(R); visit(me);   // me last (up) — needed when
                                                   //   I depend on my children's results

How to choose: if MY answer needs my children's answers (height, sum, "is balanced?"), you MUST do the work after the calls → post-order / bubble up. If I just need info from my ancestors (depth, path-so-far), pass it down as a parameter → pre-order / carry down.

9. THE 6 RECURSION SHAPES

How to recognize which one: one smaller input → Linear/Tail. Two children → Tree. "For each choice, recurse" → Multi-branch (this is backtracking). "Split in half" → Divide & Conquer. Grammar or a state machine → Mutual recursion.

// Shape 4 (multi-branch) is the bridge to backtracking: loop over choices, recurse each.
function countDownChoices(n: number, choices: number[]): number {
  if (n === 0) return 1;                 // one full way to reach 0
  let ways = 0;
  for (const c of choices) {             // ONE recursive call per choice
    if (n - c >= 0) ways += countDownChoices(n - c, choices);
  }
  return ways;                           // bubble up the total count
}

⚠️ Tail-recursion reality check (interview gotcha): in theory a tail call needs O(1) stack, but JavaScript/TypeScript engines (V8, Node) do NOT optimize tail calls — only Safari's JSC does. So in practice every recursive call still costs a stack frame, and deep recursion (depth ≳ 10⁴–10⁵) overflows regardless of tail position. If depth can be large, convert to a loop or an explicit stack (§15). Treat "tail recursion is free" as true for the math, false for the runtime you'll code in.

10. PATTERN: LINEAR RECURSION

One smaller call, combine with the current element. The workhorse. If you can do these four cold, you understand the core loop of recursion.

// factorial — base 1 (multiplicative identity), combine with *
function factorial(n: number): number {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

// power a^n in O(log n) via "fast exponentiation" — D&C flavored linear
function power(a: number, n: number): number {
  if (n === 0) return 1;
  const half = power(a, Math.floor(n / 2));   // compute ONCE, reuse — don't call twice!
  return n % 2 === 0 ? half * half : half * half * a;
}

// reverse a string — base "", combine by moving head to the back
function reverse(s: string): string {
  if (s.length <= 1) return s;
  return reverse(s.slice(1)) + s[0];
}

// reverse a linked list — return type is the new HEAD node
class ListNode { val = 0; next: ListNode | null = null; }
function reverseList(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) return head;  // base: 0 or 1 node
  const newHead = reverseList(head.next);  // trust: rest is reversed, newHead is its tail-end
  head.next.next = head;                    // make the next node point back to me
  head.next = null;                         // I become the new tail
  return newHead;                           // the head never changes as it bubbles up
}

11. PATTERN: TREE / BINARY RECURSION

Two calls, combine the two results. Trees are where recursion feels natural — the structure is literally recursive (a tree is a node plus two smaller trees). Almost always post-order / bubble up.

// Each: contract → base → combine. Same skeleton, different combine.
function maxDepth(node: TreeNode | null): number {           // LC 104
  if (node === null) return 0;
  return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}

function sumTree(node: TreeNode | null): number {            // sum of all values
  if (node === null) return 0;
  return node.val + sumTree(node.left) + sumTree(node.right);
}

function invert(node: TreeNode | null): TreeNode | null {    // LC 226 — return type is a node
  if (node === null) return null;
  const L = invert(node.left);
  node.left = invert(node.right);
  node.right = L;
  return node;
}

function sameTree(p: TreeNode | null, q: TreeNode | null): boolean {  // LC 100 — boolean combine with &&
  if (p === null && q === null) return true;
  if (p === null || q === null) return false;
  return p.val === q.val && sameTree(p.left, q.left) && sameTree(p.right, q.right);
}

🔑 The "return one thing but track another" trap (e.g. tree diameter, LC 543). When the value you must return to your parent differs from the value you must report globally, return the first and update a closure variable for the second. This pattern appears constantly in tree interviews.

function diameterOfBinaryTree(root: TreeNode | null): number {  // LC 543
  let best = 0;
  function depth(node: TreeNode | null): number {  // RETURNS depth; SIDE-EFFECT updates `best`
    if (node === null) return 0;
    const L = depth(node.left);
    const R = depth(node.right);
    best = Math.max(best, L + R);   // path THROUGH this node (the thing we report)
    return 1 + Math.max(L, R);      // depth (the thing the parent needs)
  }
  depth(root);
  return best;
}

12. PATTERN: DIVIDE & CONQUER

Split in half, solve each half (trust it), merge. The recursion does the splitting; your real work is the merge step. Cost follows T(n) = 2·T(n/2) + (merge cost).

// merge sort — split, sort halves (trust), merge two sorted lists.  O(n log n)
function mergeSort(a: number[]): number[] {
  if (a.length <= 1) return a;                       // base: 0/1 element is already sorted
  const mid = a.length >> 1;
  const L = mergeSort(a.slice(0, mid));              // trust: returns sorted left
  const R = mergeSort(a.slice(mid));                 // trust: returns sorted right
  return merge(L, R);                                // the ONLY real work
}
function merge(L: number[], R: number[]): number[] {
  const out: number[] = []; let i = 0, j = 0;
  while (i < L.length && j < R.length) out.push(L[i] <= R[j] ? L[i++] : R[j++]);
  while (i < L.length) out.push(L[i++]);
  while (j < R.length) out.push(R[j++]);
  return out;
}

// binary search — throw away half each call.  T(n)=T(n/2)+O(1) → O(log n)
function bsearch(a: number[], target: number, lo = 0, hi = a.length - 1): number {
  if (lo > hi) return -1;                            // base: empty range → not found
  const mid = (lo + hi) >> 1;
  if (a[mid] === target) return mid;
  return a[mid] < target ? bsearch(a, target, mid + 1, hi)
                         : bsearch(a, target, lo, mid - 1);
}

13. PATTERN: PICK / SKIP (subsequences)

"For each element, two choices: take it or leave it." This single idea generates subsets, subsequences, knapsack, and combination sums — and it's the cleanest on-ramp from plain recursion into backtracking and DP.

// All subsets via PICK/SKIP — Style B (carry down: build `path`, collect at base).
function subsets(nums: number[]): number[][] {
  const res: number[][] = [];
  function go(i: number, path: number[]): void {
    if (i === nums.length) { res.push([...path]); return; }  // base: decided every element → record (COPY!)
    // CHOICE 1 — skip nums[i]
    go(i + 1, path);
    // CHOICE 2 — pick nums[i]
    path.push(nums[i]);
    go(i + 1, path);
    path.pop();                 // UNDO so the skip-branch above isn't polluted (backtracking)
  }
  go(0, []);
  return res;
}

// Same idea as a COUNT via Style A (bubble up) — "how many subsets sum to target?"
function countSubsetsSum(nums: number[], i: number, target: number): number {
  if (i === nums.length) return target === 0 ? 1 : 0;          // decided every element → did we land on target?
  const skip = countSubsetsSum(nums, i + 1, target);           // don't take nums[i]
  const pick = countSubsetsSum(nums, i + 1, target - nums[i]); // take nums[i]
  return skip + pick;                          // combine the two universes
}

See the bridge: add an undo after the pick branch → backtracking (full enumeration of valid paths). Add a memo keyed on (i, target) to the count version → DP. Same recursion, three destinations. Deep-dive in the Backtracking and DP sheets.

14. PASSING STATE DOWN — params vs return vs closure

THREE WAYS TO MOVE INFORMATION THROUGH A RECURSION
─────────────────────────────────────────────────────────────
1) RETURN VALUE   info flows UP    "what did my children find?"
                  → use for: results you combine (Style A)

2) PARAMETER      info flows DOWN  "what do my ancestors know?"
                  → use for: index, depth, path-so-far, running
                    sum, remaining capacity (accumulator pattern)

3) CLOSURE / outer info flows BOTH "global best / result list"
   variable        → use for: a single answer many frames update
                     (max so far, results[]), or to avoid threading
                     the same array through every call.

PICK BY ASKING: who needs this info?
   parent only        → RETURN it
   descendants only   → pass as PARAMETER
   everybody / one
   shared answer      → CLOSURE variable

// Root-to-leaf path sums (LC 257-style) — depth & path ride DOWN as params,
// results collected via a CLOSURE array, base case records the finished path.
function binaryTreePaths(root: TreeNode | null): string[] {
  const res: string[] = [];
  function dfs(node: TreeNode | null, path: number[]): void {
    if (node === null) return;
    path.push(node.val);                                   // choose
    if (node.left === null && node.right === null) {        // leaf → finished path
      res.push(path.join("->"));
    } else {
      dfs(node.left, path);
      dfs(node.right, path);
    }
    path.pop();                                            // UNDO (so siblings start clean)
  }
  dfs(root, []);
  return res;
}

⚠️ Copy vs reference — the silent killer. When you collect a mutable array into a results list, push a copy ([...path]). Pushing the array itself stores a live reference that later pop()s will mutate, and every entry ends up empty/identical.

15. RECURSION ↔ ITERATION

Every recursion is a loop + a stack. The runtime's call stack is a stack. Convert when input is huge (avoid stack overflow) or when an interviewer asks for the iterative version.

// Recursive DFS …
function dfsRec(node: TreeNode | null, out: number[]): void {
  if (node === null) return;
  out.push(node.val);            // preorder
  dfsRec(node.left, out);
  dfsRec(node.right, out);
}

// … same traversal, explicit stack (push RIGHT first so LEFT pops first)
function dfsIter(root: TreeNode | null): number[] {
  const out: number[] = [];
  if (root === null) return out;
  const stack: TreeNode[] = [root];
  while (stack.length) {
    const node = stack.pop()!;
    out.push(node.val);
    if (node.right) stack.push(node.right);  // mirror the call order
    if (node.left)  stack.push(node.left);
  }
  return out;
}

CONVERSION RECIPE
  • tail recursion        → plain while-loop, update the params
  • linear recursion      → loop, often with an accumulator
  • tree / branching DFS  → explicit stack of "frames" (state)
  • BFS / level-order     → use a QUEUE instead of a stack
WHEN TO BOTHER
  • depth can exceed ~10^4–10^5 → risk of stack overflow → go iterative
  • otherwise recursion is usually clearer; keep it.

16. MEMOIZATION (the bridge to DP)

If your recursion recomputes the same input, cache it. Plain recursion + a cache = top-down DP. You don't redesign anything — you wrap the same function.

fib(5) WITHOUT memo — the same subtrees recomputed (exponential)
                fib(5)
            /            \
        fib(4)          fib(3)
        /    \          /    \
    fib(3)  fib(2)   fib(2)  fib(1)     ← fib(3), fib(2) computed MANY times
    ...
Recursion tree has ~2^n nodes → O(2^n).  Memo collapses it to O(n):
each distinct input computed ONCE, then read from cache.

// O(2^n) — beautiful, but recomputes everything
function fibSlow(n: number): number {
  if (n < 2) return n;
  return fibSlow(n - 1) + fibSlow(n - 2);
}

// O(n) — identical logic, one cache line added. THIS is top-down DP.
function fib(n: number, memo = new Map<number, number>()): number {
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n)!;          // 1) check cache
  const ans = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, ans);                              // 2) store before returning
  return ans;
}

Memoize when: the answer depends only on the parameters (no hidden mutable state), AND the same parameter tuple recurs. Key the cache on exactly the parameters that change. Full state-design, bottom-up tables, and space optimization live in the DP sheet.

17. COMPLEXITY OF RECURSION

Time = (number of nodes in the recursion tree) × (work per node). Space = max depth of the tree (the call stack) + space held by return values. Don't guess — write the recurrence, or count tree nodes.

RECURRENCE → COMPLEXITY (memorize this table)
┌─────────────────────────┬───────────────┬───────────────────────┐
│ RECURRENCE              │ TIME          │ EXAMPLE               │
├─────────────────────────┼───────────────┼───────────────────────┤
│ T(n)=T(n-1)+O(1)        │ O(n)          │ sum, factorial        │
│ T(n)=T(n-1)+O(n)        │ O(n^2)        │ insertion-ish, perms  │
│ T(n)=2T(n-1)+O(1)       │ O(2^n)        │ naive fib, subsets    │
│ T(n)=T(n/2)+O(1)        │ O(log n)      │ binary search         │
│ T(n)=2T(n/2)+O(1)       │ O(n)          │ tree size/height      │
│ T(n)=2T(n/2)+O(n)       │ O(n log n)    │ merge / quick sort    │
│ T(n)=k·T(n-1)+O(1)      │ O(k^n)        │ k-ary choice trees    │
│ branch^depth nodes      │ O(b^d)        │ general backtracking  │
└─────────────────────────┴───────────────┴───────────────────────┘

SPACE — people forget the stack!
  depth of recursion = frames alive at once = stack space.
  • linear recursion over n  → O(n) stack  (NOT O(1)!)
  • balanced tree            → O(log n) stack (height)
  • skewed tree / list       → O(n) stack
  Add space for the output (e.g. subsets store O(n·2^n) total).

MASTER THEOREM (quick form) for T(n)=a·T(n/b)+O(n^d):
  a < b^d → O(n^d)        (work dominated by the top)
  a = b^d → O(n^d log n)  (balanced — e.g. mergesort: a=2,b=2,d=1)
  a > b^d → O(n^(log_b a)) (work dominated by the leaves)

18. COMMON BUGS & FIXES

SYMPTOM                         CAUSE → FIX
──────────────────────────────────────────────────────────────────
"Maximum call stack exceeded"   No/unreachable base case, or no
                                progress. → ensure input strictly
                                shrinks; use >= / <= not == on indices.

Returns undefined / NaN         Forgot `return` on the recursive line.
                                `f(n-1)` ≠ `return f(n-1)`. → add return.

All results are empty/identical  Stored a REFERENCE to a mutated array.
                                → push a COPY: res.push([...path]).

Wrong answer, off by one         Base case returns wrong identity, or
                                base & recursive return DIFFERENT types.
                                → re-check Step 2 of section 6.

Backtracking gives extra junk    Forgot to UNDO (pop / unmark) after
                                the recursive call. → mirror every
                                "choose" with an "unchoose".

TLE on fib-like problems         Recomputing subproblems. → add a memo
                                (section 16) → top-down DP.

Recurses into null and crashes   Leaf-style base case but a node has
                                ONE child. → guard on `node === null`.

Computes child twice (slow)      Called f(...) twice instead of saving
                                it. → const half = f(...); use `half`.

🔑 The 30-second self-check before you run it: (1) Is there a base case for every smallest input? (2) Does every recursive call get a strictly smaller argument? (3) Does every code path return the right type? (4) If I mutate shared state, do I undo it and copy on collect? Four yeses → it almost certainly works.

19. KEYWORD → APPROACH MAP

➕ Parsing with recursion, level 2 — Basic Calculator III (LC 772)

// 772 Basic Calculator III — recursion replaces the explicit stack for '(' … ')'
function calculate(s: string): number {
  let i = 0;
  const isDigit = (c: string) => c >= '0' && c <= '9';
  const parse = (): number => {
    const stack: number[] = [];
    let num = 0, op = '+';
    while (i < s.length) {
      const c = s[i++];
      if (isDigit(c)) num = num * 10 + (+c);
      else if (c === '(') num = parse();                      // the whole (...) becomes ONE operand
      if ((!isDigit(c) && c !== ' ' && c !== '(') || i === s.length) {
        if (op === '+') stack.push(num);
        else if (op === '-') stack.push(-num);
        else if (op === '*') stack.push(stack.pop()! * num);   // * and / fold immediately (precedence)
        else if (op === '/') stack.push(Math.trunc(stack.pop()! / num));
        op = c; num = 0;
      }
      if (c === ')') break;                                    // finished this parenthesis level
    }
    return stack.reduce((a, b) => a + b, 0);
  };
  return parse();
}

➕ Build by wrapping — Strobogrammatic Number II (LC 247)

// 247 Strobogrammatic Number II — build from the middle outward
function findStrobogrammatic(n: number): string[] {
  const gen = (m: number): string[] => {
    if (m === 0) return [''];
    if (m === 1) return ['0', '1', '8'];
    const pairs = [['1', '1'], ['6', '9'], ['8', '8'], ['9', '6']];
    if (m !== n) pairs.push(['0', '0']);                      // 0…0 only for INNER layers (no leading zero)
    const res: string[] = [];
    for (const mid of gen(m - 2)) for (const [a, b] of pairs) res.push(a + mid + b);
    return res;
  };
  return gen(n);
}

20. RECURSION IS THE ENGINE OF DSA

Recursion is not a topic you finish — it's the substrate under most of the interview syllabus. Once the Leap of Faith is automatic, these "separate" topics stop being separate: each is recursion with one extra idea bolted on. This is why mastering recursion pays off everywhere.

DSA TOPIC          = RECURSION THAT …                          HERE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Tree problems      … recurses on node.left and node.right       §11
Divide & conquer   … splits in half, solves each, merges        §12
Backtracking       … loops over choices + UNDOes after each     §13 → backtracking.html
Top-down DP        … caches answers so repeats are free         §16 → dp.html
Graph DFS          … recurses on neighbors with a visited set   §9  → graph.html
Subsets/perms      … makes a pick/skip choice per element       §13
Sorting (merge/qk) … divide & conquer on the array              §12
Binary search      … recurses on the surviving half             §12

THE PUNCHLINE: if you can answer "what does f return, and how do I
build it from f(smaller)?" — you can do ALL of the above. They differ
only in WHAT you carry down (a choice, a cache key, a visited set) and
WHAT you do on the way up (combine, count, collect, undo).

21. SELF-TEST — ACTIVE RECALL

Reading recursion ≠ being able to write it. Cover the right column. If you can produce these from memory, you're interview-ready. If any one stalls you, that's your signal for which section to re-read. Redo this weekly until it's instant.

Then write these cold (no peeking, in TypeScript): (1) reverse a string, (2) max depth of a binary tree, (3) all subsets of [1,2,3], (4) climb-stairs count with a memo, (5) merge sort. If you can produce all five start-to-finish, you can recurse at interview level — the rest is just recognizing which shape (§9) the new problem is.