Recursion Patterns Cheatsheet

Core Concepts

1. Base Cases

function factorial(n) {
    // Base case
    if (n <= 1) return 1;
    
    // Recursive case
    return n * factorial(n - 1);
}

2. Recursive Structure

function recursiveFunction(input) {
    // 1. Base cases
    if (baseCase) return baseValue;
    
    // 2. Process current level
    let current = processCurrentLevel(input);
    
    // 3. Recursive call with smaller input
    let subResult = recursiveFunction(smallerInput);
    
    // 4. Combine results
    return combineResults(current, subResult);
}

Common Patterns

1. Linear Recursion

Direct recursive call with smaller input.

// Sum array elements
function sum(arr, index = 0) {
    if (index === arr.length) return 0;
    return arr[index] + sum(arr, index + 1);
}

// String reversal
function reverse(str) {
    if (str.length <= 1) return str;
    return reverse(str.slice(1)) + str[0];
}

2. Binary Recursion

Two recursive calls in each function.

// Fibonacci sequence
function fibonacci(n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// Binary tree traversal
function traverse(node) {
    if (!node) return;
    traverse(node.left);
    traverse(node.right);
}

3. Tail Recursion

Recursive call is the last operation.

// Factorial with tail recursion
function factorialTail(n, acc = 1) {
    if (n <= 1) return acc;
    return factorialTail(n - 1, n * acc);
}

// Sum with tail recursion
function sumTail(arr, index = 0, acc = 0) {
    if (index === arr.length) return acc;
    return sumTail(arr, index + 1, acc + arr[index]);
}

4. Multiple Recursion

Multiple recursive calls at different positions.

// Generate all permutations
function permutations(arr) {
    if (arr.length <= 1) return [arr];
    
    const result = [];
    for (let i = 0; i < arr.length; i++) {
        const current = arr[i];
        const remaining = [...arr.slice(0, i), ...arr.slice(i + 1)];
        const perms = permutations(remaining);
        
        for (let perm of perms) {
            result.push([current, ...perm]);
        }
    }
    
    return result;
}

// Generate all subsets
function subsets(arr) {
    if (arr.length === 0) return [[]];
    
    const first = arr[0];
    const rest = arr.slice(1);
    const subsWithoutFirst = subsets(rest);
    const subsWithFirst = subsWithoutFirst.map(sub => [first, ...sub]);
    
    return [...subsWithoutFirst, ...subsWithFirst];
}

5. Backtracking

Try different paths and undo if not valid.

// N-Queens Problem
function solveNQueens(n) {
    const board = Array(n).fill().map(() => Array(n).fill('.'));
    const result = [];
    
    function isValid(row, col) {
        // Check column
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') return false;
        }
        
        // Check diagonal
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] === 'Q') return false;
        }
        
        // Check anti-diagonal
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] === 'Q') return false;
        }
        
        return true;
    }
    
    function backtrack(row) {
        if (row === n) {
            result.push(board.map(row => row.join('')));
            return;
        }
        
        for (let col = 0; col < n; col++) {
            if (isValid(row, col)) {
                board[row][col] = 'Q';
                backtrack(row + 1);
                board[row][col] = '.';
            }
        }
    }
    
    backtrack(0);
    return result;
}

6. Divide and Conquer

Split problem into smaller subproblems.

// Merge Sort
function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    
    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)];
}

Optimization Techniques

1. Memoization

Cache results to avoid redundant calculations.

// Fibonacci with memoization
function fibMemo(n, memo = new Map()) {
    if (n <= 1) return n;
    if (memo.has(n)) return memo.get(n);
    
    const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    memo.set(n, result);
    return result;
}

2. Path Recording

Keep track of path during recursion.

// Find all paths in binary tree
function findPaths(root) {
    const paths = [];
    
    function dfs(node, path) {
        if (!node) return;
        
        path.push(node.val);
        
        if (!node.left && !node.right) {
            paths.push([...path]);
        }
        
        dfs(node.left, path);
        dfs(node.right, path);
        path.pop();
    }
    
    dfs(root, []);
    return paths;
}

3. State Management

Pass state through recursive calls.

// Tree max path sum
function maxPathSum(root) {
    let maxSum = -Infinity;
    
    function dfs(node) {
        if (!node) return 0;
        
        const left = Math.max(0, dfs(node.left));
        const right = Math.max(0, dfs(node.right));
        
        maxSum = Math.max(maxSum, node.val + left + right);
        
        return node.val + Math.max(left, right);
    }
    
    dfs(root);
    return maxSum;
}

Common Pitfalls and Solutions

1. Stack Overflow

// Problem
function infinity(n) {
    return infinity(n + 1); // Will cause stack overflow
}

// Solution: Add base case
function safe(n, limit = 1000) {
    if (n >= limit) return n;
    return safe(n + 1, limit);
}

2. Redundant Calculations

// Problem
function slowFib(n) {
    if (n <= 1) return n;
    return slowFib(n - 1) + slowFib(n - 2); // Many redundant calls
}

// Solution: Use memoization
const fastFib = (n, memo = new Map()) => {
    if (n <= 1) return n;
    if (memo.has(n)) return memo.get(n);
    
    const result = fastFib(n - 1, memo) + fastFib(n - 2, memo);
    memo.set(n, result);
    return result;
};

3. Incorrect Base Case

// Problem
function factorial(n) {
    if (n == 0) return 0; // Wrong base case
    return n * factorial(n - 1);
}

// Solution
function factorial(n) {
    if (n <= 1) return 1; // Correct base case
    return n * factorial(n - 1);
}

Testing Recursive Functions

// Unit tests for recursive functions
function testRecursion() {
    // Test base cases
    console.assert(factorial(0) === 1, "factorial(0) should be 1");
    console.assert(factorial(1) === 1, "factorial(1) should be 1");
    
    // Test recursive cases
    console.assert(factorial(5) === 120, "factorial(5) should be 120");
    
    // Test edge cases
    console.assert(factorial(-1) === 1, "factorial(-1) should be 1");
}