Bài 6: Đệ Quy Và Quay Lui¶

Tác giả: FPTOJ Team
Nội dung tham khảo từ: VNOI Wiki - Đệ quy và thuật toán quay lui

Bản chất vấn đề¶

Đệ quy là gì?¶

Đệ quy (Recursion) là kỹ thuật một hàm tự gọi chính nó để giải quyết bài toán. Bài toán lớn được chia thành các bài toán con nhỏ hơn có cùng cấu trúc, cho đến khi gặp trường hợp cơ sở (base case) — điểm dừng đệ quy.

Ví dụ kinh điển: tính giai thừa \(n!\)

\[n! = n \times (n-1)! \quad \text{với} \quad 0! = 1\]

Để tính \(5!\), ta cần \(4!\), để tính \(4!\) ta cần \(3!\), và cứ tiếp tục cho đến \(0! = 1\).

Quay lui là gì?¶

Quay lui (Backtracking) là kỹ thuật thử tất cả các khả năng tại mỗi bước, đánh dấu lựa chọn, đệ quy sang bước tiếp, sau đó khôi phục trạng thái (quay lui) để thử lựa chọn khác.

Quay lui thường được sử dụng để:

Liệt kê tất cả hoán vị, tổ hợp, tập con
Giải bài toán tìm kiếm mê cung
Giải các bài toán ràng buộc (constraint satisfaction) như N-Queens, Sudoku

Khi nào sử dụng?¶

Tình huống	Phương pháp
Bài toán có thể chia thành bài toán con cùng dạng	Đệ quy
Cần liệt kê tất cả nghiệm thỏa mãn	Quay lui
\(N \leq 15\) và cần duyệt toàn bộ	Quay lui hoặc bitmask
Cần tìm nghiệm tốt nhất với nhánh cận	Quay lui + cắt tỉa

Tư duy cốt lõi¶

Nguyên tắc của đệ quy¶

Mọi hàm đệ quy phải tuân thủ hai nguyên tắc:

Phải có base case — điều kiện dừng đệ quy, nếu không sẽ tràn stack
Phần đệ quy phải gọi bài toán nhỏ hơn — đảm bảo tiến dần về base case

Cây đệ quy cho \(5!\) được minh họa như sau:

graph TD
    A["factorial(5)"] --> B["5 × factorial(4)"]
    B --> C["4 × factorial(3)"]
    C --> D["3 × factorial(2)"]
    D --> E["2 × factorial(1)"]
    E --> F["factorial(1) = 1<br/>(base case)"]
    F --> G["return 1"]
    G --> H["return 2 × 1 = 2"]
    H --> I["return 3 × 2 = 6"]
    I --> J["return 4 × 6 = 24"]
    J --> K["return 5 × 24 = 120"]

Template quay lui¶

Mọi bài toán quay lui đều tuân theo một khuôn mẫu chung:

graph TD
    A["Gọi hàm backtrack(trạng thái hiện tại)"] --> B{"Đã tìm được nghiệm?"}
    B -- "Có" --> C["Lưu/in nghiệm"]
    B -- "Không" --> D["Duyệt từng lựa chọn khả thi"]
    D --> E["Thêm lựa chọn vào lời giải"]
    E --> F["Đệ quy: backtrack(trạng thái mới)"]
    F --> G["Quay lui: loại bỏ lựa chọn"]
    G --> D

Ba bước cốt lõi lặp lại tại mỗi node trên cây tìm kiếm:

Chọn (Choose) — thử một lựa chọn khả thi
Khám phá (Explore) — đệ quy sang trạng thái tiếp
Bỏ chọn (Unchoose) — khôi phục trạng thái cũ (đây chính là "quay lui")

Ví dụ minh họa: Sinh hoán vị \(\{1, 2, 3\}\)¶

Cây tìm kiếm khi sinh tất cả hoán vị của tập \(\{1, 2, 3\}\):

graph TD
    R["[]"] --> A1["[1]"]
    R --> A2["[2]"]
    R --> A3["[3]"]
    A1 --> B12["[1,2]"]
    A1 --> B13["[1,3]"]
    A2 --> B21["[2,1]"]
    A2 --> B23["[2,3]"]
    A3 --> B31["[3,1]"]
    A3 --> B32["[3,2]"]
    B12 --> L1["[1,2,3] ✓"]
    B13 --> L2["[1,3,2] ✓"]
    B21 --> L3["[2,1,3] ✓"]
    B23 --> L4["[2,3,1] ✓"]
    B31 --> L5["[3,1,2] ✓"]
    B32 --> L6["[3,2,1] ✓"]

Tổng cộng \(3! = 6\) hoán vị. Mỗi lá trên cây là một nghiệm hoàn chỉnh.

Bài toán N-Queens¶

Xếp \(N\) quân hậu lên bàn cờ \(N \times N\) sao cho không hai quân hậu nào ăn nhau (không cùng hàng, cột, đường chéo).

Ý tưởng: Xếp hậu theo từng hàng. Hàng \(i\): thử từng cột \(j\), kiểm tra tính hợp lệ bằng 3 mảng đánh dấu:

col[j] — cột \(j\) đã có hậu chưa
diag1[i + j] — đường chéo chính (tổng \(i+j\) cố định trên mỗi đường chéo)
diag2[i - j + N] — đường chéo phụ (hiệu \(i-j\) cố định, cộng \(N\) để tránh chỉ số âm)

Phân tích tính đúng đắn¶

Tại sao đệ quy đúng?¶

Đệ quy đúng khi thỏa mãn hai điều kiện:

Base case đúng: Giá trị trả về ở trường hợp cơ sở là chính xác. Ví dụ: \(0! = 1\) là đúng theo định nghĩa.
Bước đệ quy đúng: Giả sử hàm đúng cho input nhỏ hơn (giả thuyết đệ quy), thì công thức đệ quy cho ra kết quả đúng cho input hiện tại.

Với giai thừa: Giả sử factorial(n-1) trả về đúng \((n-1)!\), thì factorial(n) = n × factorial(n-1) = n × (n-1)! = n! đúng.

Tại sao quay lui đúng?¶

Quay lui đúng vì nó duyệt toàn bộ không gian tìm kiếm mà không bỏ sót:

Tại mỗi bước, tất cả lựa chọn khả thi đều được thử
Sau mỗi lần thử, trạng thái được khôi phục hoàn toàn (bước quay lui)
Do đó, lựa chọn tiếp theo không bị ảnh hưởng bởi lựa chọn trước

Ví dụ: Trong sinh hoán vị, nếu quên used[num] = false sau khi đệ quy, số num sẽ bị đánh dấu "đã dùng" vĩnh viễn, khiến các nhánh sau không thể chọn num lại — kết quả bị thiếu.

Kiểm tra correctness bằng ví dụ¶

Với bài toán tổ hợp có lặp (subset sum), sử dụng startIdx đảm bảo mỗi tổ hợp chỉ được sinh một lần (không sinh trùng hoán vị khác thứ tự). Nếu dùng i = 0 thay vì i = startIdx, ta sẽ sinh ra các tổ hợp trùng lặp.

Đánh giá độ phức tạp¶

Đệ quy đơn giản¶

Bài toán	Độ phức tạp thời gian	Độ phức tạp không gian
Giai thừa \(n!\)	\(O(n)\)	\(O(n)\) (stack)
Fibonacci không nhớ	\(O(2^n)\)	\(O(n)\) (stack)
Fibonacci có nhớ (memoization)	\(O(n)\)	\(O(n)\)

Fibonacci không nhớ có độ phức tạp \(O(2^n)\) vì mỗi hàm gọi đệ quy 2 lần, tạo thành cây nhị phân với số node tăng theo cấp số nhân.

Quay lui¶

Giả sử tại mỗi bước có \(k\) lựa chọn, độ sâu cây tìm kiếm là \(d\):

Trường hợp tổng quát: \(O(k^d)\) — duyệt toàn bộ cây tìm kiếm
Với nhánh cận (pruning): Có thể giảm đáng kể tùy bài toán

Độ phức tạp cụ thể cho các bài toán kinh điển:

Bài toán	Thời gian	Không gian
Sinh hoán vị \(n\) phần tử	\(O(n!)\)	\(O(n)\)
Sinh tổ hợp \(C(n, k)\)	\(O\left(\binom{n}{k}\right)\)	\(O(k)\)
N-Queens	\(O(n!)\) (với nhánh cận)	\(O(n)\)

Tại sao N-Queens là \(O(n!)\)?¶

Ở hàng đầu tiên có \(n\) lựa chọn, hàng thứ hai tối đa \(n-1\) (bị loại bỏ cột và đường chéo), hàng thứ ba tối đa \(n-2\), và cứ tiếp tục. Tổng: \(n \times (n-1) \times \ldots \times 1 = n!\). Nhánh cận (cắt bỏ các vị trí không hợp lệ) giúp thực tế chạy nhanh hơn nhiều so với cận trên này.

So sánh: Đệ quy vs. Quay lui vs. Quy hoạch động¶

Tiêu chí	Đệ quy	Quay lui	Quy hoạch động
Mục đích	Chia bài toán con	Liệt kê/tìm nghiệm	Tối ưu hóa
Có nhớ (memo)?	Có thể	Không	Có
Không gian	\(O(\text{độ sâu})\)	\(O(\text{độ sâu})\)	\(O(\text{số trạng thái})\)
Thời gian	Tùy bài toán	\(O(k^d)\)	\(O(\text{số trạng thái} \times \text{transition})\)

Code minh họa¶

Bài toán 1: Tính giai thừa¶

Đệ quy cơ bản nhất. Công thức: \(n! = n \times (n-1)!\) với \(0! = 1\).

C++Python

#include <bits/stdc++.h>
using namespace std;

// Bước 1: nếu n == 0 thì dừng (trường hợp cơ sở)
// Bước 2: ngược lại, thu nhỏ bài toán: n! = n * (n-1)!
long long factorial(int n) {
    if (n == 0) return 1; // cơ sở: 0! = 1, điểm dừng đệ quy
    return factorial(n - 1) * n; // gọi bài toán nhỏ hơn (n-1), rồi nhân thêm n
}

int main() {
    cout << factorial(5) << "\n"; // 120
    return 0;
}

def factorial(n):
    # Bước 1: nếu n == 0 thì dừng (trường hợp cơ sở)
    if n == 0:
        return 1
    # Bước 2: thu nhỏ bài toán: n! = n * (n-1)!
    return factorial(n - 1) * n

print(factorial(5))  # 120

Bài toán 2: Số Fibonacci¶

Công thức: \(F(n) = F(n-1) + F(n-2)\) với \(F(0) = 0\), \(F(1) = 1\).

Đệ quy trực tiếp có độ phức tạp \(O(2^n)\) vì tính lại cùng một giá trị nhiều lần. Dùng memoization để giảm xuống \(O(n)\).

C++Python

#include <bits/stdc++.h>
using namespace std;

// Đệ quy thuần: O(2^n) - chậm!
// Lý do: mỗi n sinh 2 nhánh, tính lại cùng giá trị nhiều lần
long long fibo_slow(int n) {
    if (n <= 1) return n; // cơ sở: F(0)=0, F(1)=1
    return fibo_slow(n - 1) + fibo_slow(n - 2); // chia thành 2 bài toán con nhỏ hơn
}

// Memoization: O(n)
// memo[n] = -1 nghĩa là chưa tính; đã tính thì trả ngay, khỏi đệ quy lại
long long memo[100];
long long fibo(int n) {
    if (n <= 1) return n; // cơ sở
    if (memo[n] != -1) return memo[n]; // bước nhớ: đã có đáp án thì dùng lại
    memo[n] = fibo(n - 1) + fibo(n - 2); // bước khám phá + lưu vào bảng nhớ
    return memo[n]; // trả đáp án đã lưu
}

int main() {
    memset(memo, -1, sizeof(memo));
    cout << fibo(10) << "\n"; // 55
    return 0;
}

from functools import lru_cache

@lru_cache(maxsize=None)
def fibo(n):
    if n <= 1:
        return n
    return fibo(n - 1) + fibo(n - 2)

print(fibo(10))  # 55

Bài toán 3: Sinh tất cả hoán vị¶

Template quay lui cơ bản. Dùng mảng used đánh dấu số đã chọn, sau mỗi lần đệ quy phải bỏ đánh dấu (quay lui).

C++Python

#include <bits/stdc++.h>
using namespace std;

int n;
int perm[20]; // perm[pos] = số đang đặt ở vị trí pos
bool used[20]; // used[num] = true nghĩa là số num đã nằm trong perm

void generate(int pos) {
    // Bước 1 (cơ sở): đã điền đủ n vị trí → in 1 hoán vị
    if (pos > n) {
        for (int i = 1; i <= n; i++)
            cout << perm[i] << " ";
        cout << "\n";
        return;
    }
    // Bước 2 (thử): duyệt từng số num chưa dùng
    for (int num = 1; num <= n; num++) {
        if (!used[num]) {
            perm[pos] = num; // bước chọn: đặt num vào vị trí pos
            used[num] = true; // bước đánh dấu: num đã được dùng
            generate(pos + 1); // bước khám phá: đệ quy điền vị trí tiếp theo
            used[num] = false; // bước quay lui: bỏ đánh dấu để nhánh sau dùng lại num
        }
    }
}

int main() {
    n = 3;
    generate(1);
    // Output: 123, 132, 213, 231, 312, 321
    return 0;
}

def generate_permutation(n):
    used = [False] * (n + 1)  # used[num] = True nghĩa là num đã nằm trong perm
    perm = []  # perm đang xây dở, độ dài = vị trí đang điền

    def backtrack():
        # Bước 1 (cơ sở): đủ n số → in 1 hoán vị
        if len(perm) == n:
            print(*perm)
            return
        # Bước 2 (thử): duyệt từng số chưa dùng
        for num in range(1, n + 1):
            if not used[num]:
                perm.append(num)  # bước chọn: thêm num vào cuối
                used[num] = True  # bước đánh dấu
                backtrack()  # bước khám phá: đệ quy sâu hơn
                perm.pop()  # bước quay lui: bỏ num ra khỏi perm
                used[num] = False  # bước quay lui: mở lại num cho nhánh sau

    backtrack()

generate_permutation(3)
# Output: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1

Trace stack tay `generate` với `n = 3` (nhánh `[1]` đầu tiên)¶

Bước	Gọi hàm (stack)	`perm` hiện tại	`used`	Hành động
1	`generate(1)`	`[]`	`{}`	thử `num=1` → chọn 1
2	`generate(2)`	`[1]`	`{1}`	thử `num=1` bị dùng, bỏ qua; chọn `num=2`
3	`generate(3)`	`[1,2]`	`{1,2}`	`num=1,2` đã dùng; chọn `num=3`
4	`generate(4)`	`[1,2,3]`	`{1,2,3}`	`pos > n` → in `1 2 3`, return
5	về `generate(3)`	`[1,2]`	`{1,2}`	quay lui: gỡ 3; hết `num` → return
6	về `generate(2)`	`[1]`	`{1}`	quay lui: gỡ 2; chọn tiếp `num=3`
7	`generate(3)`	`[1,3]`	`{1,3}`	chọn `num=2` (số duy nhất còn trống)
8	`generate(4)`	`[1,3,2]`	`{1,3,2}`	`pos > n` → in `1 3 2`, return

Quy luật: mỗi lần return là 1 lần "quay lui" (gỡ số cuối, mở lại used), rồi vòng for thử số tiếp theo.

Bài toán 4: N-Queens¶

Xếp \(N\) hậu lên bàn cờ \(N \times N\). Dùng 3 mảng boolean kiểm tra cột, đường chéo chính, đường chéo phụ.

C++Python

#include <bits/stdc++.h>
using namespace std;

int n;
bool col[20], diag1[40], diag2[40]; // col[j]: cột j đã có hậu; diag1/2: 2 đường chéo đã bị chiếm
int queenPos[20]; // queenPos[row] = cột đặt hậu ở hàng row

void solve(int row) {
    // Bước 1 (cơ sở): xếp xong n hàng → in 1 nghiệm
    if (row > n) {
        for (int i = 1; i <= n; i++)
            cout << queenPos[i] << " ";
        cout << "\n";
        return;
    }
    // Bước 2 (thử): duyệt từng cột ở hàng hiện tại
    for (int col_idx = 1; col_idx <= n; col_idx++) {
        int d1 = row + col_idx; // chỉ số đường chéo chính (tổng cố định)
        int d2 = row - col_idx + 20; // chỉ số đường chéo phụ (+20 để không âm)
        if (col[col_idx] || diag1[d1] || diag2[d2])
            continue; // bước cắt tỉa: ô bị ăn thì bỏ qua
        queenPos[row] = col_idx; // bước chọn: đặt hậu
        col[col_idx] = diag1[d1] = diag2[d2] = true; // bước đánh dấu 3 hướng
        solve(row + 1); // bước khám phá: xếp hàng tiếp theo
        col[col_idx] = diag1[d1] = diag2[d2] = false; // bước quay lui: gỡ hậu ra
    }
}

int main() {
    n = 8;
    solve(1);
    return 0;
}

def solve_n_queens(n):
    col_used = [False] * n  # cột nào đã có hậu
    diag1 = [False] * (2 * n)  # đường chéo chính theo tổng row+c
    diag2 = [False] * (2 * n)  # đường chéo phụ theo hiệu row-c+n
    queens = []  # queens[row] = cột đặt hậu

    def backtrack(row):
        # Bước 1 (cơ sở): xếp xong n hàng → in nghiệm
        if row == n:
            print(queens)
            return
        # Bước 2 (thử): duyệt từng cột ở hàng row
        for c in range(n):
            d1 = row + c
            d2 = row - c + n
            if col_used[c] or diag1[d1] or diag2[d2]:
                continue  # bước cắt tỉa: ô bị ăn thì bỏ
            queens.append(c)  # bước chọn
            col_used[c] = diag1[d1] = diag2[d2] = True  # bước đánh dấu
            backtrack(row + 1)  # bước khám phá
            queens.pop()  # bước quay lui: gỡ hậu
            col_used[c] = diag1[d1] = diag2[d2] = False  # bước quay lui: mở lại 3 hướng

    backtrack()

solve_n_queens(4)

Bài toán 5: Tổ hợp có lặp (Subset Sum)¶

Tìm tất cả cách chọn số từ mảng sao cho tổng bằng target. Dùng startIdx để tránh sinh trùng tổ hợp.

C++Python

#include <bits/stdc++.h>
using namespace std;

int coins[15], coinCount; // coins: các mệnh giá; coinCount: số loại
long long target; // tổng mục tiêu cần đạt
vector<int> cur; // cur: cách chọn đang xây dở

void findWays(int startIdx, long long curSum) {
    // Bước 1 (cơ sở): tổng vừa đủ target → in 1 cách
    if (curSum == target) {
        for (int x : cur) cout << x << " ";
        cout << "\n";
        return;
    }
    // Bước 2 (thử): duyệt từ startIdx để không sinh trùng thứ tự
    for (int i = startIdx; i < coinCount; i++) {
        if (curSum + coins[i] <= target) { // bước cắt tỉa: vượt target thì bỏ
            cur.push_back(coins[i]); // bước chọn: lấy thêm 1 đồng coins[i]
            findWays(i, curSum + coins[i]); // bước khám phá: truyền i (cho lặp) + tổng mới
            cur.pop_back(); // bước quay lui: bỏ đồng vừa lấy
        }
    }
}

int main() {
    coinCount = 4;
    coins[0] = 2; coins[1] = 3; coins[2] = 5; coins[3] = 7;
    target = 10;
    findWays(0, 0);
    return 0;
}

def find_ways(coins, target):
    cur = []  # cách chọn đang xây dở

    def backtrack(start, cur_sum):
        # Bước 1 (cơ sở): tổng vừa đủ → in 1 cách
        if cur_sum == target:
            print(cur)
            return
        # Bước 2 (thử): duyệt từ start để không sinh trùng
        for i in range(start, len(coins)):
            if cur_sum + coins[i] <= target:  # bước cắt tỉa: vượt target thì bỏ
                cur.append(coins[i])  # bước chọn
                backtrack(i, cur_sum + coins[i])  # bước khám phá (truyền i cho lặp)
                cur.pop()  # bước quay lui

    backtrack(0, 0)

find_ways([2, 3, 5, 7], 10)

Cạm bẫy thường gặp¶

Bẫy 1: Quên base case¶

Không có base case dẫn đến đệ quy vô hạn và tràn stack.

C++Python

// SAI: không có base case
int factorial(int n) {
    return factorial(n - 1) * n;
}

// ĐÚNG: phải có base case
int factorial(int n) {
    if (n == 0) return 1;
    return factorial(n - 1) * n;
}

# SAI: không có base case
def factorial(n):
    return factorial(n - 1) * n

# ĐÚNG: phải có base case
def factorial(n):
    if n == 0:
        return 1
    return factorial(n - 1) * n

Bẫy 2: Quên bước quay lui¶

Sau khi đệ quy, phải khôi phục trạng thái. Nếu quên, các nhánh sau sẽ bị ảnh hưởng.

C++Python

// SAI: quên khôi phục used[num]
used[num] = true;
backtrack(pos + 1);
// used[num] vẫn = true → nhánh khác không dùng được num!

// ĐÚNG: phải khôi phục
used[num] = true;
backtrack(pos + 1);
used[num] = false;

# SAI: quên khôi phục used[num]
used[num] = True
backtrack(pos + 1)
# used[num] vẫn = True → nhánh khác không dùng được num!

# ĐÚNG: phải khôi phục
used[num] = True
backtrack(pos + 1)
used[num] = False

Bẫy 3: Tràn stack khi đệ quy sâu¶

Mỗi lần gọi hàm đệ quy, một frame mới được đẩy vào stack. Với \(N\) lớn (ví dụ \(N = 100000\)), stack sẽ tràn.

Giải pháp: Dùng memoization, chuyển sang đệ quy đuôi (tail recursion), hoặc viết lại bằng vòng lặp.

Bẫy 4: Đệ quy Fibonacci không nhớ — \(O(2^n)\)¶

Đây là lỗi phổ biến nhất. Hàm fibo(n) gọi cả fibo(n-1) và fibo(n-2), dẫn đến tính lại cùng một giá trị nhiều lần.

C++Python

// SAI: O(2^n) - rất chậm với n lớn
long long fibo(int n) {
    if (n <= 1) return n;
    return fibo(n - 1) + fibo(n - 2);
}

// ĐÚNG: dùng memoization - O(n)
long long memo[100];
long long fibo(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fibo(n - 1) + fibo(n - 2);
    return memo[n];
}

from functools import lru_cache

@lru_cache(maxsize=None)
def fibo(n):
    if n <= 1:
        return n
    return fibo(n - 1) + fibo(n - 2)

Bài tập luyện tập¶

Mã bài	Tên bài tập	Độ khó	Kiểu bài tập (Bản chất)
`rec-fact`	Tính giai thừa	⭐	Đệ quy
`rec-fibo`	Số Fibonacci	⭐	Đệ quy có nhớ
`rec-power`	Lũy thừa bằng đệ quy	⭐	Đệ quy
`rec-digit`	Đếm chữ số	⭐	Đệ quy
`rec-gcd`	GCD bằng đệ quy	⭐	Đệ quy Euclid
`rec-binary`	Xâu nhị phân	⭐⭐	Quay lui
`rec-perm`	Hoán vị	⭐⭐	Quay lui
`rec-comb`	Tổ hợp	⭐⭐	Quay lui
`rec-subsetsum`	Tổng tập con	⭐⭐	Quay lui
`rec-maze`	Đếm đường đi	⭐⭐	Đệ quy
`rec-nqueen`	N-Queens	⭐⭐⭐	Quay lui
`rec-knap`	Knapsack vét cạn	⭐⭐⭐	Quay lui + nhánh cận
`rec-coin`	Đổi tổng	⭐⭐⭐	Quay lui
`rec-partition`	Phân hoạch số	⭐⭐⭐	Quay lui
`rec-tower`	Tháp Hà Nội	⭐⭐⭐	Đệ quy
`rec-sudoku`	Sudoku	⭐⭐⭐⭐⭐	Quay lui
`rec-mcolor`	Tô màu đồ thị	⭐⭐⭐⭐⭐	Quay lui

Bài viết liên quan¶

Tài liệu tham khảo¶

Bài tiếp theo: Mảng, Stack, Prefix Sum →

Bài 6: Đệ Quy Và Quay Lui¶

Bản chất vấn đề¶

Đệ quy là gì?¶

Quay lui là gì?¶

Khi nào sử dụng?¶

Tư duy cốt lõi¶

Nguyên tắc của đệ quy¶

Template quay lui¶

Ví dụ minh họa: Sinh hoán vị \(\{1, 2, 3\}\)¶

Bài toán N-Queens¶

Phân tích tính đúng đắn¶

Tại sao đệ quy đúng?¶

Tại sao quay lui đúng?¶

Kiểm tra correctness bằng ví dụ¶

Đánh giá độ phức tạp¶

Đệ quy đơn giản¶

Quay lui¶

Tại sao N-Queens là \(O(n!)\)?¶

So sánh: Đệ quy vs. Quay lui vs. Quy hoạch động¶

Code minh họa¶

Bài toán 1: Tính giai thừa¶

Bài toán 2: Số Fibonacci¶

Bài toán 3: Sinh tất cả hoán vị¶

Trace stack tay generate với n = 3 (nhánh [1] đầu tiên)¶

Bài toán 4: N-Queens¶

Bài toán 5: Tổ hợp có lặp (Subset Sum)¶

Cạm bẫy thường gặp¶

Bẫy 1: Quên base case¶

Bẫy 2: Quên bước quay lui¶

Bẫy 3: Tràn stack khi đệ quy sâu¶

Bẫy 4: Đệ quy Fibonacci không nhớ — \(O(2^n)\)¶

Bài tập luyện tập¶

Bài viết liên quan¶

Tài liệu tham khảo¶

💬 Bình luận

Trace stack tay `generate` với `n = 3` (nhánh `[1]` đầu tiên)¶