Recursion

The base case is the condition that stops recursion. It returns a value directly without making another recursive call, preventing infinite recursion.

function sum(n) {
    if (n === 0) return 0;  // base case: stop here
    return n + sum(n - 1);  // recursive case
}
// sum(4) => 4 + 3 + 2 + 1 + 0 = 10

// Without base case:
// sum(4) -> sum(3) -> sum(2) -> ... forever!

A good base case is simple, reachable, and handles the smallest valid input.

Factorial: n! = n × (n-1)! with base case 0! = 1.

function factorial(n) {
    if (n <= 1) return 1;     // base case
    return n * factorial(n - 1); // recursive step
}
// factorial(5) => 5 * 4 * 3 * 2 * 1 = 120

// Call stack: factorial(5)
//   5 * factorial(4)
//     4 * factorial(3)
//       3 * factorial(2)
//         2 * factorial(1) => 1

Time: O(n)  |  Space: O(n) due to call stack

Naive recursive Fibonacci has exponential time due to repeated calculations. Add memoization to make it O(n).

// Naive — O(2^n)
function fib(n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

// Memoized — O(n)
function fibMemo(n, memo = {}) {
    if (n <= 1) return n;
    if (memo[n]) return memo[n];
    return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}
// fibMemo(10) => 55

Memoization caches results of subproblems to avoid redundant work.

Tower of Hanoi: Move n disks from source to target using an auxiliary peg. Move n-1 disks to auxiliary, move the largest to target, then move n-1 from auxiliary to target.

function hanoi(n, from, to, aux) {
    if (n === 1) {
        console.log(from + " -> " + to);
        return;
    }
    hanoi(n - 1, from, aux, to);
    console.log(from + " -> " + to);
    hanoi(n - 1, aux, to, from);
}
// hanoi(3, "A", "C", "B")
// Moves: 2^n - 1 = 7 moves for 3 disks

Moves: 2ⁿ - 1  |  Time: O(2ⁿ)

The power set contains all possible subsets. For each element, either include it or exclude it.

function powerSet(arr, idx = 0, current = []) {
    if (idx === arr.length) {
        console.log(current);
        return;
    }
    // Include arr[idx]
    powerSet(arr, idx + 1, [...current, arr[idx]]);
    // Exclude arr[idx]
    powerSet(arr, idx + 1, current);
}
// powerSet([1, 2, 3])
// [], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]

Total subsets: 2ⁿ  |  Time: O(2ⁿ)

Fix one character at a time and recursively permute the rest. Swap each character into the current position.

function permutations(str, l = 0, r = str.length - 1) {
    if (l === r) { console.log(str); return; }
    const arr = str.split("");
    for (let i = l; i <= r; i++) {
        [arr[l], arr[i]] = [arr[i], arr[l]];
        permutations(arr.join(""), l + 1, r);
        [arr[l], arr[i]] = [arr[i], arr[l]]; // backtrack
    }
}
// permutations("abc") => abc, acb, bac, bca, cba, cab

Total: n! permutations  |  Time: O(n × n!)

Recursive binary search divides the search range by half on each call. The base case is when the range is empty.

function binarySearchRec(arr, target, lo = 0, hi = arr.length - 1) {
    if (lo > hi) return -1; // base case
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target)
        return binarySearchRec(arr, target, mid + 1, hi);
    return binarySearchRec(arr, target, lo, mid - 1);
}
// binarySearchRec([1,3,5,7,9], 7) => 3

Time: O(log n)  |  Space: O(log n) due to call stack

Add the first element to the recursive sum of the rest of the array. Base case: empty array returns 0.

function sumArray(arr, i = 0) {
    if (i === arr.length) return 0;  // base case
    return arr[i] + sumArray(arr, i + 1);
}
// sumArray([1, 2, 3, 4, 5]) => 15

// Trace: 1 + sumArray([2,3,4,5])
//        1 + 2 + sumArray([3,4,5])
//        1 + 2 + 3 + sumArray([4,5])
//        1 + 2 + 3 + 4 + sumArray([5])
//        1 + 2 + 3 + 4 + 5 + 0 = 15

Time: O(n)  |  Space: O(n) call stack

Check each element: if it is an array, recursively flatten it; otherwise, add it to the result.

function flatten(arr) {
    const result = [];
    for (const item of arr) {
        if (Array.isArray(item)) {
            result.push(...flatten(item));
        } else {
            result.push(item);
        }
    }
    return result;
}
// flatten([1, [2, [3, 4], 5], [6, 7]])
// => [1, 2, 3, 4, 5, 6, 7]

Time: O(n) where n = total elements  |  Space: O(d) where d = max depth

Move n-1 disks from source to auxiliary (using destination), move the largest disk to destination, then move n-1 disks from auxiliary to destination (using source).

function hanoi(n, from, to, aux) {
    if (n === 0) return;
    hanoi(n - 1, from, aux, to); // move n-1 disks to auxiliary
    console.log("Move disk " + n + " from " + from + " to " + to);
    hanoi(n - 1, aux, to, from); // move n-1 disks from auxiliary to target
}
// Input: n=1 => Output: "Move disk 1 from A to C"  (1 move)
// Input: n=2 => Output: 3 moves (A->B, A->C, B->C)
// Input: n=3 => Output: 7 moves (2^n - 1)
// Input: n=10 => Output: 1023 moves

Time: O(2ⁿ) — minimum moves = 2ⁿ - 1  |  Space: O(n) recursion depth

Place queens row by row. For each row, try each column — only proceed if no existing queen shares the column, or a diagonal.

function solveNQueens(n) {
    const result = [];
    const cols = new Set(), diag1 = new Set(), diag2 = new Set();
    const board = Array.from({length: n}, () => new Array(n).fill('.'));
    function backtrack(row) {
        if (row === n) {
            result.push(board.map(r => r.join('')));
            return;
        }
        for (let col = 0; col < n; col++) {
            if (cols.has(col) || diag1.has(row-col) || diag2.has(row+col)) continue;
            board[row][col] = 'Q';
            cols.add(col); diag1.add(row-col); diag2.add(row+col);
            backtrack(row + 1);
            board[row][col] = '.';
            cols.delete(col); diag1.delete(row-col); diag2.delete(row+col);
        }
    }
    backtrack(0);
    return result;
}
// Input: n=4  => Output: 2 solutions
// Input: n=8  => Output: 92 solutions

Time: O(n!)  |  Space: O(n) for tracking sets

Fix each element at the current position by swapping it with all elements from current to end. Recurse, then unswap (backtrack).

function permutations(nums) {
    const result = [];
    function backtrack(start) {
        if (start === nums.length) { result.push([...nums]); return; }
        for (let i = start; i < nums.length; i++) {
            [nums[start], nums[i]] = [nums[i], nums[start]]; // swap
            backtrack(start + 1);
            [nums[start], nums[i]] = [nums[i], nums[start]]; // unswap
        }
    }
    backtrack(0);
    return result;
}
// Input: [1,2,3]  => Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]
// Input: [1,2]    => Output: [[1,2],[2,1]]
// Input: [1]      => Output: [[1]]

Time: O(n! × n)  |  Space: O(n) recursion depth (not counting output)

GCD uses Euclid's algorithm: gcd(a, b) = gcd(b, a mod b). LCM = (a × b) / gcd(a, b).

function gcd(a, b) {
    return b === 0 ? a : gcd(b, a % b);
}
function lcm(a, b) {
    return (a / gcd(a, b)) * b; // divide first to avoid overflow
}
// Input: gcd(48, 18)   => Output: 6
//   (gcd(48,18) = gcd(18,12) = gcd(12,6) = gcd(6,0) = 6)
// Input: gcd(100, 75)  => Output: 25
// Input: lcm(12, 18)   => Output: 36
// Input: lcm(4, 6)     => Output: 12

Time: O(log(min(a,b))) — Fibonacci worst case  |  Space: O(log(min(a,b)))

Recursively narrow the search space by half. Base case: lo > hi (not found) or arr[mid] equals target.

function binarySearchRecursive(arr, target, lo = 0, hi = arr.length - 1) {
    if (lo > hi) return -1; // base case: not found
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, hi);
    return binarySearchRecursive(arr, target, lo, mid - 1);
}
// Input: [1,3,5,7,9], target=7   => Output: 3 (index)
// Input: [1,3,5,7,9], target=6   => Output: -1 (not found)
// Input: [2,4,6,8,10], target=1  => Output: -1

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

For each element, you have two choices: include it or exclude it. Total subsets = 2ⁿ.

function subsets(nums) {
    const result = [];
    function backtrack(start, current) {
        result.push([...current]);
        for (let i = start; i < nums.length; i++) {
            current.push(nums[i]);
            backtrack(i + 1, current);
            current.pop(); // backtrack
        }
    }
    backtrack(0, []);
    return result;
}
// Input: [1,2,3]
// Output: [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
// (8 = 2³ subsets)
// Input: [1]   => Output: [[], [1]]

Time: O(2ⁿ × n)  |  Space: O(n) recursion depth

Divide the array in half, recursively sort both halves, then merge them. Classic divide-and-conquer with O(n log n) guaranteed.

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)];
}
// Input: [38,27,43,3,9,82,10]
// Output: [3,9,10,27,38,43,82]

Time: O(n log n)  |  Space: O(n log n) for call stack + temp arrays

Use exponentiation by squaring: x^n = (x^(n/2))² for even n, x × x^(n-1) for odd n. Reduces multiplications from O(n) to O(log n).

function myPow(x, n) {
    if (n < 0) return 1 / myPow(x, -n);
    if (n === 0) return 1;
    if (n % 2 === 0) {
        const half = myPow(x, n / 2);
        return half * half;
    }
    return x * myPow(x, n - 1);
}
// Input: x=2.00, n=10   => Output: 1024.00
// Input: x=2.10, n=3    => Output: 9.261
// Input: x=2.00, n=-2   => Output: 0.25

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

From each position, try all possible jumps. Memoize: memo[i] = can we reach the end from index i?

function canJump(nums) {
    const memo = new Map();
    function dp(i) {
        if (i >= nums.length - 1) return true;
        if (memo.has(i)) return memo.get(i);
        const maxJump = nums[i];
        for (let j = 1; j <= maxJump; j++) {
            if (dp(i + j)) { memo.set(i, true); return true; }
        }
        memo.set(i, false);
        return false;
    }
    return dp(0);
}
// (Greedy is O(n) but memo recursion shows the principle)
// Input: [2,3,1,1,4]  => Output: true
// Input: [3,2,1,0,4]  => Output: false (stuck at index 3)

Time: O(n²) with memoization  |  Space: O(n)

From (0,0) to (m-1,n-1) moving only right or down. Recursive relation: paths(i,j) = paths(i+1,j) + paths(i,j+1). Memoize to avoid exponential recomputation.

function uniquePaths(m, n) {
    const memo = new Map();
    function dp(r, c) {
        if (r === m - 1 || c === n - 1) return 1; // base: last row/col
        const key = r + ',' + c;
        if (memo.has(key)) return memo.get(key);
        const result = dp(r + 1, c) + dp(r, c + 1);
        memo.set(key, result);
        return result;
    }
    return dp(0, 0);
}
// Input: m=3, n=7   => Output: 28
// Input: m=3, n=2   => Output: 3
// Input: m=1, n=1   => Output: 1

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

Use backtracking: recursively build combinations. At each step, choose the next number (must be greater than the last chosen to avoid duplicates).

function combine(n, k) {
    const result = [];
    function backtrack(start, current) {
        if (current.length === k) { result.push([...current]); return; }
        // Pruning: only go up to n - (k - current.length) + 1
        const limit = n - (k - current.length) + 1;
        for (let i = start; i <= limit; i++) {
            current.push(i);
            backtrack(i + 1, current);
            current.pop();
        }
    }
    backtrack(1, []);
    return result;
}
// Input: n=4, k=2   => Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
// Input: n=1, k=1   => Output: [[1]]

Time: O(C(n,k) × k)  |  Space: O(k) recursion depth

Recursively halve the number. If it reaches 1, it's a power of 2. If it becomes odd before reaching 1, it's not. Alternatively, use bitwise: n & (n-1) === 0.

function isPowerOfTwo(n) {
    if (n <= 0) return false;
    if (n === 1) return true; // base case
    if (n % 2 !== 0) return false; // odd means not a power of 2
    return isPowerOfTwo(n / 2);
}
// Bitwise approach (O(1)):
function isPowerOfTwoBit(n) {
    return n > 0 && (n & (n - 1)) === 0;
}
// Input: n=1    => Output: true   (2^0)
// Input: n=16   => Output: true   (2^4)
// Input: n=3    => Output: false
// Input: n=218  => Output: false

Time: O(log n) recursive  |  Space: O(log n). Bitwise is O(1) time and O(1) space.

Each element C(n,k) = C(n-1,k-1) + C(n-1,k). Use memoization to avoid exponential blowup, or use the formula C(n,k) = C(n,k-1) × (n-k+1)/k.

function getRow(rowIndex) {
    const result = [1];
    for (let k = 1; k <= rowIndex; k++) {
        // C(n,k) = C(n,k-1) * (n-k+1) / k
        result.push(Math.round(result[k-1] * (rowIndex - k + 1) / k));
    }
    return result;
}
// Recursive with memo:
function comb(n, k, memo = {}) {
    if (k === 0 || k === n) return 1;
    const key = n + ',' + k;
    if (key in memo) return memo[key];
    return memo[key] = comb(n-1, k-1, memo) + comb(n-1, k, memo);
}
// Input: rowIndex=3   => Output: [1,3,3,1]
// Input: rowIndex=4   => Output: [1,4,6,4,1]
// Input: rowIndex=0   => Output: [1]

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