Chuyên đề nền tảng hiện đại

🔁 Đệ quy: Base Case, Call Stack, Memoization & DFS

Bài học này giữ kiến thức cốt lõi về đệ quy, nhưng trình bày theo hướng thực tế hơn: hiểu call stack, biết khi nào nên dùng đệ quy, khi nào nên chuyển sang vòng lặp hoặc quy hoạch động để tránh lỗi và quá thời gian.

Base caseĐiều kiện dừng bắt buộc
Call stackHiểu chương trình đang gọi gì
MemoizationĐệ quy + ghi nhớ kết quả
DFS/BacktrackingỨng dụng còn dùng nhiều
Mục tiêuKhái niệmCall stackCode mẫuHiện đạiMemoizationLỗi hay nhầmBài tập

Mục tiêu bài học

Học xong cần làm được

  • Hiểu khái niệm đệ quy: hàm tự gọi lại chính nó.
  • Nắm được hai phần quan trọng: điều kiện dừng và lời gọi thu nhỏ bài toán.
  • Hiểu vì sao không có điều kiện dừng sẽ gây tràn stack.
  • Biết phân biệt đệ quy nên dùng, đệ quy nên tránh, và đệ quy cần tối ưu bằng ghi nhớ.

Kiến thức cập nhật, thực dụng

  • Không dùng đệ quy ngây thơ cho Fibonacci lớn.
  • Không lạm dụng đệ quy cho bài chỉ cần vòng lặp đơn giản.
  • Ưu tiên memoization, iterative DP, hoặc vòng lặp khi dữ liệu lớn.
  • Đệ quy vẫn rất mạnh trong DFS, cây, chia để trị, quay lui.

1. Đệ quy là gì?

Đệ quy là cách viết hàm trong đó hàm tự gọi lại chính nó để giải một phiên bản nhỏ hơn của bài toán ban đầu. Một hàm đệ quy tốt thường có hai phần:

Điều kiện dừng

Trường hợp nhỏ nhất có thể trả lời ngay. Ví dụ: factorial(0) = 1.

Bước thu nhỏ

Gọi lại chính hàm đó với dữ liệu nhỏ hơn. Ví dụ: factorial(n - 1).

Bài toán lớn
→
Bài toán nhỏ hơn
→
Điều kiện dừng
→
Trả kết quả ngược lại
Không còn nên dạy theo kiểu “cứ gọi lại là được”. Học sinh phải luôn hỏi: dữ liệu có nhỏ đi không? Có điều kiện dừng không? Số lần gọi có quá nhiều không?

2. Mô phỏng Call Stack: factorial(n)

Mỗi lần hàm gọi lại chính nó, máy tính tạo một khung gọi hàm trên stack. Khi gặp điều kiện dừng, các khung này lần lượt trả kết quả ngược lại.

Nhấn “Bước tiếp” để xem quá trình gọi hàm.
Với n rất lớn, số khung gọi hàm cũng lớn. Vì vậy Python có giới hạn độ sâu đệ quy, còn C++ cũng có thể tràn stack nếu gọi quá sâu.

3. Code mẫu: Giai thừa n!

Ví dụ giai thừa phù hợp để học cấu trúc đệ quy, nhưng trong bài thi lớn cần chú ý tràn số. Với C++, long long chỉ lưu được một số giai thừa nhỏ.

#include 
using namespace std;

long long factorial(int n) {
    if (n == 0) return 1;              // điều kiện dừng
    return 1LL * n * factorial(n - 1); // gọi bài toán nhỏ hơn
}

int main() {
    int n;
    cin >> n;
    cout << factorial(n);
    return 0;
}
def factorial(n):
    if n == 0:
        return 1              # điều kiện dừng
    return n * factorial(n - 1)

n = int(input())
print(factorial(n))
#include 
using namespace std;

int main() {
    int n;
    cin >> n;
    long long ans = 1;
    for (int i = 1; i <= n; i++) ans *= i;
    cout << ans;
    return 0;
}

4. Dùng đệ quy đúng chỗ

Tình huốngNên làm gì?Lý doVí dụ
Bài toán có cấu trúc cây / đồ thịCó thể dùng đệ quyDFS tự nhiên, code ngắn, dễ hiểu.Duyệt cây, đếm component, DFS trên mê cung.
Bài toán chia đôiĐệ quy rất hợpMỗi bước chia thành bài toán nhỏ hơn.Merge Sort, Quick Sort, Divide and Conquer.
Bài liệt kê khả năngDùng quay luiĐệ quy giúp thử - chọn - quay lại rõ ràng.Sinh nhị phân, hoán vị, tổ hợp.
Fibonacci lớn bằng công thức đệ quy thườngKhông nênLặp lại quá nhiều lời gọi, độ phức tạp tăng rất nhanh.fib(n-1) + fib(n-2) không ghi nhớ.
Bài chỉ cần cộng từ 1 đến nƯu tiên vòng lặp / công thứcĐệ quy không làm bài đơn giản hơn, lại tăng rủi ro stack.Tổng 1..n, giai thừa n nhỏ.

5. Fibonacci: từ đệ quy cũ sang memoization

Fibonacci đệ quy ngây thơ thường được dùng để minh họa, nhưng không nên dùng cho n lớn. Cách tốt hơn là ghi nhớ kết quả đã tính, gọi là memoization.

So sánh số lời gọi ước lượng

Nhấn “So sánh” để xem vì sao Fibonacci đệ quy thường rất chậm.
# Chỉ dùng để minh họa, không dùng với n lớn

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(6))
from functools import lru_cache

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

n = int(input())
print(fib(n))
#include 
using namespace std;

int main() {
    int n;
    cin >> n;
    vector dp(n + 2, 0);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    cout << dp[n];
    return 0;
}

6. Mẫu tư duy khi viết đệ quy

Bước 1

Xác định bài toán nhỏ nhất

Ví dụ sum(1)=1, factorial(0)=1, cây rỗng thì kết quả là 0.

Bước 2

Viết công thức thu nhỏ

Ví dụ sum(n)=n+sum(n-1). Dữ liệu phải tiến dần về điều kiện dừng.

Bước 3

Ước lượng số lần gọi

Nếu số lời gọi lặp lại quá nhiều, cần memoization, DP hoặc cách khác.

7. Lỗi học sinh hay nhầm

Quên điều kiện dừng.
Hàm gọi mãi không kết thúc, dẫn đến tràn stack.
Tham số không nhỏ đi.
Ví dụ gọi factorial(n) bên trong chính factorial(n) thì không bao giờ tiến về điều kiện dừng.
Dùng Fibonacci đệ quy thường cho n lớn.
Cần memoization hoặc DP lặp.
Nghĩ đệ quy luôn tốt hơn vòng lặp.
Với bài đơn giản như tính tổng, vòng lặp hoặc công thức thường rõ và an toàn hơn.
Không chú ý giới hạn stack.
DFS rất sâu hoặc n quá lớn có thể cần chuyển sang stack tự quản lý hoặc vòng lặp.

8. Bài tập luyện tập phân loại

📘 Mức 1 - Cơ bản

  1. Tính giai thừa của n bằng đệ quy.
  2. Tính tổng từ 1 đến n bằng đệ quy.
  3. In các số từ n về 1 bằng đệ quy.

📗 Mức 2 - Hiểu call stack

  1. Viết lại quá trình gọi hàm của factorial(4).
  2. Đếm số lần gọi hàm khi tính sum_recursive(5).
  3. Sửa một hàm đệ quy bị thiếu điều kiện dừng.

📙 Mức 3 - Ứng dụng còn dùng nhiều

  1. Dùng DFS đệ quy để đếm số đỉnh trong một component.
  2. Sinh tất cả xâu nhị phân độ dài n.
  3. Dùng quay lui sinh các tổ hợp chập k.

🐉 Mức 4 - HSG định hướng

  1. Fibonacci với memoization.
  2. Đệ quy chia để trị: tìm max trong đoạn [l,r].
  3. DFS cây tính kích thước mỗi subtree.
💡 Xem lời giải mẫu: Tổng 1..n bằng đệ quy
#include 
using namespace std;

long long sum_recursive(int n) {
    if (n == 0) return 0;
    return n + sum_recursive(n - 1);
}

int main() {
    int n;
    cin >> n;
    cout << sum_recursive(n);
    return 0;
}
def sum_recursive(n):
    if n == 0:
        return 0
    return n + sum_recursive(n - 1)

n = int(input())
print(sum_recursive(n))

9. Quiz kiểm tra nhanh

Câu 1. Phần nào bắt buộc phải có trong hàm đệ quy để tránh gọi vô hạn?
Câu 2. Fibonacci đệ quy thường chậm vì:
Câu 3. Bài nào sau đây thường hợp với đệ quy?

Tổng kết

Đệ quy không lỗi thời, nhưng cách học cần hiện đại hơn: hiểu call stack, luôn có điều kiện dừng, biết ước lượng số lời gọi, và biết thay đệ quy ngây thơ bằng memoization, DP hoặc vòng lặp khi cần. Đệ quy vẫn là công cụ rất mạnh trong DFS, cây, chia để trị và quay lui.

➡ Tiếp theo: Quay lui - dùng đệ quy để thử các khả năng một cách có kiểm soát.

⬅️ Quay lại chương 5