🔄 JavaScript Recursion Patterns

Parent: Recursion & Backtracking Index

---

Overview

---

Pattern 1 — Tower of Hanoi

Problem: Move n disks from rod A to rod C using B as helper. Larger disk can never go on smaller.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Move top n-1 to helper → move disk n to dest → move n-1 from helper to dest.

Step 2 — Algorithm:

1. Base case: n=1 → print move

2. hanoi(n-1, from, via, to)

3. Print "Move disk n: from → to"

4. hanoi(n-1, via, to, from)

function hanoi(n, from, to, via) {
    if (n === 1) {
        console.log(`Move disk 1: ${from} → ${to}`);
        return;
    }

    hanoi(n - 1, from, via, to); // Move top n-1 to helper
    console.log(`Move disk ${n}: ${from} → ${to}`);
    hanoi(n - 1, via, to, from); // Move n-1 from helper to dest
}

hanoi(3, 'A', 'C', 'B');
// Move disk 1: A → C
// Move disk 2: A → B
// Move disk 1: C → B
// Move disk 3: A → C
// ...

Time: O(2ⁿ) — 2ⁿ-1 total moves | Space: O(n)

---

Pattern 2 — Generate All Subsets

Problem: Return all possible subsets (power set) of an array.

---

🧠 How to Approach This

Step 1 — Binary decision tree:

Each element → include OR exclude → 2ⁿ subsets total.

Step 2 — Algorithm:

1. At each index: include element, recurse, pop (backtrack), recurse without

2. Base case: index == array length → push copy to result

function subsets(nums) {
    const result  = [];
    const current = [];

    function generate(idx) {
        // Base case: processed all elements
        if (idx === nums.length) {
            result.push([...current]); // push a copy
            return;
        }

        // Choice 1: INCLUDE nums[idx]
        current.push(nums[idx]);
        generate(idx + 1);

        // Choice 2: EXCLUDE nums[idx]
        current.pop();
        generate(idx + 1);
    }

    generate(0);
    return result;
}

console.log(subsets([1, 2, 3]));
// [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]] — 8 subsets

Time: O(2ⁿ) | Space: O(n)

---

Pattern 3 — Generate All Permutations

Problem: Return all permutations of an array.

---

🧠 How to Approach This

Step 1 — Swap approach:

Fix one element at position start by swapping with each position j >= start. Recurse. Swap back.

Step 2 — Algorithm:

1. Base case: start == length → push copy

2. For j from start to end: swap(start, j), recurse(start+1), swap back

function permutations(nums) {
    const result = [];

    function permute(start) {
        if (start === nums.length) {
            result.push([...nums]); // copy current arrangement
            return;
        }

        for (let j = start; j < nums.length; j++) {
            // Choose: fix nums[j] at position start
            [nums[start], nums[j]] = [nums[j], nums[start]];

            // Explore
            permute(start + 1);

            // Un-choose (restore)
            [nums[start], nums[j]] = [nums[j], nums[start]];
        }
    }

    permute(0);
    return result;
}

console.log(permutations([1, 2, 3]));
// [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]

Time: O(n × n!) | Space: O(n)

---

Pattern 4 — Combination Sum

Problem: Find all combinations that sum to target. Each number may be used unlimited times.

---

🧠 How to Approach This

Step 1 — Unlimited pick backtracking:

At each step: use current candidate again (same index) OR skip to next. Sort for early pruning.

Step 2 — Algorithm:

1. Base: target == 0 → found combination

2. Base: target < 0 or index out of bounds → prune

3. For i from start: if candidates[i] > target → break (sorted)

- push, recurse(i, target-candidates[i]), pop

function combinationSum(candidates, target) {
    candidates.sort((a, b) => a - b);
    const result  = [];
    const current = [];

    function backtrack(start, remaining) {
        if (remaining === 0) { result.push([...current]); return; }

        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) break; // sorted — prune

            current.push(candidates[i]);
            backtrack(i, remaining - candidates[i]); // same i — reuse
            current.pop();
        }
    }

    backtrack(0, target);
    return result;
}

console.log(combinationSum([2, 3, 6, 7], 7)); // [[2,2,3],[7]]
console.log(combinationSum([2, 3, 5], 8));     // [[2,2,2,2],[2,3,3],[3,5]]

Time: O(n^(T/M)) | Space: O(T/M)

---

Pattern 5 — Binary Search (Recursive)

Problem: Implement binary search recursively.

---

🧠 How to Approach This

Step 1: Divide search space in half each call.

function binarySearch(arr, target, left = 0, right = arr.length - 1) {
    if (left > right) return -1; // Base case: not found

    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return mid;
    if (target < arr[mid])   return binarySearch(arr, target, left, mid - 1);
    return binarySearch(arr, target, mid + 1, right);
}

console.log(binarySearch([1, 3, 5, 7, 9, 11], 7)); // 3
console.log(binarySearch([1, 3, 5, 7, 9, 11], 6)); // -1

Time: O(log n) | Space: O(log n)

---

Pattern 6 — Merge Sort (Recursive)

Problem: Sort using merge sort (divide and conquer).

---

🧠 How to Approach This

Step 1 — Divide: Split into halves recursively until single elements.

Step 2 — Conquer: Merge two sorted halves.

function mergeSort(arr) {
    if (arr.length <= 1) return arr; // Base case

    const mid   = Math.floor(arr.length / 2);
    const left  = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

function merge(left, right) {
    const result = [];
    let i = 0, j = 0;

    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) result.push(left[i++]);
        else                      result.push(right[j++]);
    }

    return [...result, ...left.slice(i), ...right.slice(j)];
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]

Time: O(n log n) | Space: O(n)

---

Pattern Summary