Recursion

// 1) Classic — factorial
function factorial(n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

// 2) Fibonacci — exponential without memo
function fib(n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);     // O(2^n) — slow
}

// With memoisation — O(n)
function fibMemo(n, memo = new Map()) {
    if (n < 2) return n;
    if (memo.has(n)) return memo.get(n);
    const v = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    memo.set(n, v);
    return v;
}

// 3) Walk a tree
class Node { constructor(v, children = []) { this.v = v; this.children = children; } }

function printTree(node, indent = 0) {
    console.log(' '.repeat(indent) + node.v);
    for (const c of node.children) printTree(c, indent + 2);
}

// Sum values in a tree
function sum(node) {
    return node.v + node.children.reduce((s, c) => s + sum(c), 0);
}

// 4) Binary tree traversals
function inorder(node, visit) {
    if (!node) return;
    inorder(node.left, visit);
    visit(node.v);
    inorder(node.right, visit);
}

function preorder(node, visit) {
    if (!node) return;
    visit(node.v);
    preorder(node.left, visit);
    preorder(node.right, visit);
}

function postorder(node, visit) {
    if (!node) return;
    postorder(node.left, visit);
    postorder(node.right, visit);
    visit(node.v);
}

// 5) Tree depth
function depth(node) {
    if (!node) return 0;
    return 1 + Math.max(depth(node.left), depth(node.right));
}

// 6) Divide and conquer — merge sort
function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    const mid = arr.length >> 1;
    const left  = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    return merge(left, right);
}

function merge(a, b) {
    const out = [];
    let i = 0, j = 0;
    while (i < a.length && j < b.length) {
        if (a[i] <= b[j]) out.push(a[i++]);
        else              out.push(b[j++]);
    }
    return [...out, ...a.slice(i), ...b.slice(j)];
}

// 7) Quicksort
function quickSort(arr) {
    if (arr.length <= 1) return arr;
    const pivot = arr[0];
    const less    = arr.slice(1).filter(x => x <  pivot);
    const equal   = arr.filter   (x => x === pivot);
    const greater = arr.slice(1).filter(x => x >  pivot);
    return [...quickSort(less), ...equal, ...quickSort(greater)];
}

// 8) Backtracking — generate all subsets
function subsets(nums) {
    const out = [];
    function recurse(i, current) {
        if (i === nums.length) { out.push([...current]); return; }
        recurse(i + 1, current);                    // skip
        current.push(nums[i]);
        recurse(i + 1, current);                    // include
        current.pop();
    }
    recurse(0, []);
    return out;
}

// 9) Backtracking — permutations
function permutations(nums) {
    const out = [];
    function recurse(current, used) {
        if (current.length === nums.length) { out.push([...current]); return; }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.push(nums[i]);
            recurse(current, used);
            current.pop();
            used[i] = false;
        }
    }
    recurse([], new Array(nums.length).fill(false));
    return out;
}

// 10) N-queens
function nQueens(n) {
    const out = [];
    const cols = new Set(), d1 = new Set(), d2 = new Set();
    const board = Array.from({ length: n }, () => Array(n).fill('.'));
    function recurse(row) {
        if (row === n) {
            out.push(board.map(r => r.join('')));
            return;
        }
        for (let c = 0; c < n; c++) {
            if (cols.has(c) || d1.has(row + c) || d2.has(row - c)) continue;
            cols.add(c); d1.add(row + c); d2.add(row - c);
            board[row][c] = 'Q';
            recurse(row + 1);
            board[row][c] = '.';
            cols.delete(c); d1.delete(row + c); d2.delete(row - c);
        }
    }
    recurse(0);
    return out;
}

// 11) Graph DFS
function dfs(graph, start) {
    const visited = new Set();
    function recurse(node) {
        if (visited.has(node)) return;
        visited.add(node);
        console.log(node);
        for (const n of graph[node] ?? []) recurse(n);
    }
    recurse(start);
}

// 12) Recursion vs iteration
// Iteration is generally faster + uses less stack.
// Recursion is clearer for: tree traversal, divide-and-conquer, backtracking.
// Stack overflow is real — JS default limit ~10k frames. Don't recurse on million-item arrays.

// 13) Tail recursion (PSA: JS doesn't optimise it; many languages do)
// Tail call: the recursive call is the LAST thing the function does.
function factorialTail(n, acc = 1) {
    if (n <= 1) return acc;
    return factorialTail(n - 1, n * acc);    // tail call (in TCO languages, no extra stack frame)
}
// Languages with TCO: Scheme, Erlang, Elixir, Scala (partial), Lua, OCaml.
// Without TCO, you still risk stack overflow.

// 14) Convert recursion → iteration with a stack
function iterDfs(node) {
    const stack = [node];
    while (stack.length) {
        const n = stack.pop();
        if (!n) continue;
        console.log(n.v);
        stack.push(n.right, n.left);          // push right first so left processes first
    }
}

// 15) When to use recursion
// - Natural fit: tree / graph / divide-and-conquer / backtracking
// - Problem state collapses to a smaller version of itself
// - Memoise overlapping subproblems (DP)
//
// When to convert to iteration
// - Deep recursion (millions of frames) → stack overflow
// - Hot path performance — iteration is usually faster
// - You see overlapping subproblems → memoise OR build a table bottom-up

// 16) Common pitfalls
//   • Forgetting the base case → infinite recursion → stack overflow
//   • Mutating shared state across calls without proper backtracking
//   • Recomputing the same subproblems → exponential time (memoise!)
//   • Deep recursion in async code → 'too much recursion' errors
//   • Trampolining can help in JS: convert tail-call recursion into a while loop returning closures

function fact(n) { return n <= 1 ? 1 : n * fact(n - 1); }
// Use a stack or trampoline if you might overflow.