Recursion &
Backtracking

6.1 Đệ quy là gì?

Đệ quy (recursion) = một hàm gọi chính nó với input nhỏ hơn. Ý tưởng: "để giải bài toán cỡ n, ta giả sử đã giải được cho cỡ n-1, rồi từ đó ráp ra đáp án cho n."

Mọi hàm đệ quy phải có 2 thành phần:

1. Base case: điều kiện dừng — khi bài toán đủ nhỏ để giải trực tiếp
2. Recursive case: gọi chính nó với input nhỏ hơn, sau đó kết hợp kết quả

// Tính giai thừa n!
function factorial(n) {
  if (n <= 1) return 1;        // base case
  return n * factorial(n - 1); // recursive case
}

factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1
= 120

Tại sao đệ quy "hoạt động"?

Mỗi lời gọi đệ quy được lưu trên call stack. Mỗi frame có biến cục bộ riêng, không ảnh hưởng đến frame khác. Khi base case return, frame được pop, kết quả truyền ngược lên.

Call stack (đệ quy factorial(3)):

[factorial(1), n=1]   ← top, return 1
[factorial(2), n=2]      → return 2 * 1 = 2
[factorial(3), n=3]      → return 3 * 2 = 6
[main()]              ← bottom

6.2 Tư duy đệ quy — 3 bước viết hàm đệ quy

Khi viết hàm đệ quy, không cần "imagine" toàn bộ stack. Chỉ cần 3 bước:

1. Định nghĩa rõ "hàm này làm gì" với input cụ thể.
2. Xác định base case: input cỡ nào thì giải trực tiếp được?
3. Giả sử hàm đã đúng cho input nhỏ hơn, ráp ra đáp án cho input hiện tại.

Ví dụ: tính tổng mảng

// Bước 1: sumArray(arr) trả về tổng các phần tử của arr
// Bước 2: base case — mảng rỗng → 0
// Bước 3: giả sử sumArray(arr.slice(1)) đúng
//          → kết quả = arr[0] + sumArray(arr.slice(1))

function sumArray(arr) {
  if (arr.length === 0) return 0;
  return arr[0] + sumArray(arr.slice(1));
}

// sumArray([1,2,3,4]) = 1 + sumArray([2,3,4])
//                     = 1 + 2 + sumArray([3,4])
//                     = 1 + 2 + 3 + sumArray([4])
//                     = 1 + 2 + 3 + 4 + sumArray([])
//                     = 1 + 2 + 3 + 4 + 0 = 10

Lưu ý: code trên có space O(n²) vì slice tạo array mới mỗi lần. Cải tiến: dùng index thay vì slice.

function sumArray(arr, i = 0) {
  if (i === arr.length) return 0;
  return arr[i] + sumArray(arr, i + 1);
}
// Time O(n), Space O(n) cho call stack

Ví dụ: Đảo ngược chuỗi

// reverse(s) đảo ngược chuỗi s
// Base case: s rỗng → ""
// Recursive: reverse(s.slice(1)) + s[0]

function reverse(s) {
  if (s.length <= 1) return s;
  return reverse(s.slice(1)) + s[0];
}
// reverse("hello") = reverse("ello") + "h"
//                  = (reverse("llo") + "e") + "h"
//                  = "olleh"

6.3 Recursion Tree — vẽ ra để tính Big-O

Nhiều hàm đệ quy gọi chính nó nhiều lần. Để tính Big-O, ta vẽ recursion tree.

Ví dụ: Fibonacci đệ quy ngây thơ

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

                    fib(5)
                   /        \
              fib(4)         fib(3)
              /    \         /    \
          fib(3)  fib(2)  fib(2)  fib(1)
          /  \    /  \    /  \
      fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
      /  \
  fib(1) fib(0)

Phân tích: recursion tree có ~2ⁿ node → O(2ⁿ) time, O(n) space (depth của cây). Với n=30 đã thấy chậm rõ. Với n=50, chạy mất hàng giờ.

Tại sao chậm?

Vì rất nhiều subproblem được tính lặp đi lặp lại: fib(2) được tính 3 lần, fib(1) 5 lần, ... Đây là dấu hiệu của overlapping subproblems — bài này có thể tối ưu bằng Memoization (xem 6.5).

Công thức tổng quát: Master Theorem

Cho recursion T(n) = a · T(n/b) + f(n), có 3 trường hợp:

Áp dụng cho Merge Sort: T(n) = 2T(n/2) + O(n) → trường hợp 2 → O(n log n).

6.4 Tail Recursion — đệ quy đuôi

Tail recursion = lời gọi đệ quy là phép tính cuối cùng trong hàm (không có phép cộng/trừ/... sau lời gọi đệ quy).

// KHÔNG phải tail recursion — có "n *" sau lời gọi
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);  // ← không phải call cuối
}

// Tail recursion — dùng accumulator
function factorialTail(n, acc = 1) {
  if (n <= 1) return acc;
  return factorialTail(n - 1, acc * n);  // ← call cuối
}

Một số ngôn ngữ (Scheme, Scala, Haskell) tối ưu tail recursion bằng Tail Call Optimization (TCO): không tạo frame mới, biến đệ quy thành vòng lặp → O(1) space.

6.5 Memoization — cache kết quả

Khi đệ quy có overlapping subproblems, dùng cache để tránh tính lại. Đây là cầu nối từ Recursion sang Dynamic Programming (Chương 12).

Fibonacci với memoization

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  return memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
}

// Time: O(n) — mỗi fib(k) tính đúng 1 lần
// Space: O(n) — memo + call stack

Sự khác biệt: fib(50) không memo chạy ~1 phút; có memo ~1 ms.

Hàm decorator memoize tổng quát

function memoize(fn) {
  const cache = new Map();
  return function(...args) {
    const key = JSON.stringify(args);
    if (cache.has(key)) return cache.get(key);
    const result = fn.apply(this, args);
    cache.set(key, result);
    return result;
  };
}

const fastFib = memoize(function fib(n) {
  if (n <= 1) return n;
  return fastFib(n - 1) + fastFib(n - 2);
});

6.6 Backtracking — đệ quy có thử-sai-quay-lui

Backtracking = đệ quy duyệt mọi nhánh, khi gặp ngõ cụt (không thoả điều kiện) thì quay lui để thử nhánh khác. Đây là kỹ thuật giải:

• Liệt kê tất cả phương án (permutations, combinations, subsets)
• Tìm phương án thoả điều kiện (N-Queens, Sudoku)
• Tối ưu trên không gian phương án (Travelling Salesman brute force)

Template tổng quát

function backtrack(state, choices) {
  if (isGoal(state)) {
    record(state);          // lưu kết quả
    return;
  }
  for (const choice of choices) {
    if (isValid(state, choice)) {
      apply(state, choice);   // thử (choose)
      backtrack(state, ...);  // đệ quy (explore)
      undo(state, choice);    // quay lui (un-choose)
    }
  }
}

3 bước: choose → explore → un-choose. Đây là điểm khác biệt với đệ quy thường (không có un-choose).

6.7 Permutations — Hoán vị

Cho mảng [1, 2, 3], liệt kê tất cả hoán vị: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].

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

  function backtrack(path, used) {
    if (path.length === nums.length) {
      result.push([...path]);  // copy vì path sẽ thay đổi
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(nums[i]);

      backtrack(path, used);

      path.pop();         // un-choose
      used[i] = false;    // un-choose
    }
  }

  backtrack([], new Array(nums.length).fill(false));
  return result;
}

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

Big-O: O(n · n!) — n! hoán vị, mỗi cái copy O(n).

Permutations II — có phần tử trùng

function permuteUnique(nums) {
  nums.sort((a, b) => a - b);  // sort để nhận biết trùng
  const result = [];

  function backtrack(path, used) {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      // Skip nếu phần tử trùng và phần tử trước chưa được dùng
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;
      used[i] = true;
      path.push(nums[i]);
      backtrack(path, used);
      path.pop();
      used[i] = false;
    }
  }

  backtrack([], new Array(nums.length).fill(false));
  return result;
}

6.8 Combinations — Tổ hợp

Khác permutation, combination không quan tâm thứ tự: [1,2] và [2,1] giống nhau.

Combinations: chọn k từ [1..n]

function combine(n, k) {
  const result = [];

  function backtrack(start, path) {
    if (path.length === k) {
      result.push([...path]);
      return;
    }
    for (let i = start; i <= n; i++) {
      path.push(i);
      backtrack(i + 1, path);  // i+1 tránh chọn lại
      path.pop();
    }
  }

  backtrack(1, []);
  return result;
}

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

Combination Sum: chọn nhiều lần được

// Cho candidates và target. Tìm các bộ phần tử (có thể trùng nhau từ candidates)
// có tổng = target. Mỗi candidate dùng được nhiều lần.
function combinationSum(candidates, target) {
  const result = [];

  function backtrack(start, path, sum) {
    if (sum === target) {
      result.push([...path]);
      return;
    }
    if (sum > target) return;
    for (let i = start; i < candidates.length; i++) {
      path.push(candidates[i]);
      // Truyền i (không phải i+1) để cho phép dùng lại
      backtrack(i, path, sum + candidates[i]);
      path.pop();
    }
  }

  backtrack(0, [], 0);
  return result;
}

// candidates = [2,3,6,7], target = 7
// → [[2,2,3], [7]]

6.9 Subsets — Tập con

Cho mảng [1, 2, 3], liệt kê tất cả 2³ = 8 tập con (kể cả [] và mảng đầy đủ).

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

  function backtrack(start, path) {
    result.push([...path]);  // mỗi state đều là 1 subset
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  }

  backtrack(0, []);
  return result;
}

// [1,2,3] →
// [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]

Cách khác: bit manipulation

// Mỗi tập con tương ứng 1 bitmask
function subsetsBit(nums) {
  const n = nums.length;
  const result = [];
  for (let mask = 0; mask < (1 << n); mask++) {
    const subset = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) subset.push(nums[i]);
    }
    result.push(subset);
  }
  return result;
}

6.10 Bài kinh điển

6.10.1 N-Queens

Đặt N quân hậu trên bàn cờ NxN sao cho không quân nào "tấn công" được quân khác.

function solveNQueens(n) {
  const result = [];
  const cols = new Set();
  const diag1 = new Set();  // r - c
  const diag2 = new Set();  // r + c
  const board = Array.from({length: n}, () => 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;
}

6.10.2 Sudoku Solver

function solveSudoku(board) {
  function isValid(r, c, ch) {
    for (let i = 0; i < 9; i++) {
      if (board[r][i] === ch) return false;
      if (board[i][c] === ch) return false;
      const br = 3 * Math.floor(r / 3) + Math.floor(i / 3);
      const bc = 3 * Math.floor(c / 3) + i % 3;
      if (board[br][bc] === ch) return false;
    }
    return true;
  }

  function backtrack() {
    for (let r = 0; r < 9; r++) {
      for (let c = 0; c < 9; c++) {
        if (board[r][c] !== '.') continue;
        for (let n = 1; n <= 9; n++) {
          const ch = String(n);
          if (isValid(r, c, ch)) {
            board[r][c] = ch;
            if (backtrack()) return true;
            board[r][c] = '.';
          }
        }
        return false;  // không số nào đặt được → quay lui
      }
    }
    return true;  // hết ô trống
  }

  backtrack();
}

6.10.3 Word Search

// Cho board ký tự và word. Có thể tìm word trên board không?
// Ô liền kề (4 hướng), không dùng lại ô.
function exist(board, word) {
  const m = board.length, n = board[0].length;

  function dfs(r, c, i) {
    if (i === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n) return false;
    if (board[r][c] !== word[i]) return false;

    const tmp = board[r][c];
    board[r][c] = '#';  // đánh dấu đã thăm

    const found = dfs(r+1, c, i+1) || dfs(r-1, c, i+1)
               || dfs(r, c+1, i+1) || dfs(r, c-1, i+1);

    board[r][c] = tmp;  // un-choose
    return found;
  }

  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      if (dfs(r, c, 0)) return true;
  return false;
}

6.10.4 Generate Parentheses

// Tạo ra tất cả chuỗi dấu ngoặc hợp lệ với n cặp.
// n=3: "((()))", "(()())", "(())()", "()(())", "()()()"
function generateParenthesis(n) {
  const result = [];

  function backtrack(open, close, path) {
    if (path.length === 2 * n) {
      result.push(path);
      return;
    }
    if (open < n) backtrack(open + 1, close, path + '(');
    if (close < open) backtrack(open, close + 1, path + ')');
  }

  backtrack(0, 0, '');
  return result;
}

Bài tập

"23" → ["ad","ae","af","bd","be","bf","cd","ce","cf"]

"25525511135" → ["255.255.11.135", "255.255.111.35"]

"aab" → [["a","a","b"], ["aa","b"]]

Tổng kết chương 6

• ✅ Đệ quy = base case + recursive case; tư duy "giả sử đã đúng cho n-1"
• ✅ Recursion tree giúp tính Big-O; nhiều subproblem trùng → dùng memoization
• ✅ JS không có TCO thực tế → đệ quy sâu vẫn tốn O(n) stack
• ✅ Backtracking = đệ quy + un-choose; template "choose → explore → un-choose"
• ✅ Permutations = n! cách; Subsets = 2ⁿ; Combinations C(n,k) bài "chọn k từ n"
• ✅ Bài kinh điển: N-Queens, Sudoku, Word Search, Generate Parentheses
• ✅ Memoization là cầu nối từ Recursion sang Dynamic Programming (Chương 12)