Đệ quy là gì? Giải thích dễ hiểu, sơ đồ ngăn xếp và code C++, Python

Đệ quy là gì? Hình dung qua việc xếp hàng đếm số thứ tự

Giả sử bạn đang đứng trong một hàng dọc rất dài và muốn biết mình đang đứng ở vị trí thứ mấy tính từ đầu hàng, nhưng bạn không được rời khỏi chỗ mà chỉ được hỏi người đứng ngay trước mặt mình:

• Bạn hỏi người phía trước: "Bạn đứng thứ mấy?" rồi lấy câu trả lời cộng thêm 1.
• Người đó cũng chưa biết, lại hỏi tiếp người đứng trước họ câu y hệt.
• Cứ thế câu hỏi truyền lên đến người đầu hàng. Người đầu hàng nhìn phía trước không còn ai, trả lời ngay: "Tôi đứng thứ 1!" (không cần hỏi ai nữa).
• Từ con số 1 đó, người thứ hai cộng 1 trả lời 2, người thứ ba trả lời 3,..., cho đến khi kết quả truyền ngược về tới bạn.

Quá trình trên chính là đệ quy (recursion): giải một bài toán kích thước n bằng cách nhờ lời giải của bài toán nhỏ hơn n - 1 có cùng bản chất, cho tới khi chạm tới trường hợp nhỏ nhất biết sẵn đáp án.

Hai thành phần bắt buộc của mọi hàm đệ quy

Khi viết bất kỳ hàm đệ quy nào bằng C++ hay Python, bạn luôn phải kiểm tra đủ 2 phần:

1. Trường hợp cơ sở (Base case — điều kiện dừng): Khi dữ liệu đầu vào đã đủ nhỏ (ví dụ n == 0 hoặc n == 1), hàm trả về kết quả ngay lập tức mà không gọi đệ quy thêm nữa.
2. Bước đệ quy (Recursive step): Biểu diễn lời giải của bài toán cỡ n thông qua lời gọi hàm với đầu vào nhỏ hơn (ví dụ n - 1 hoặc n / 2), đảm bảo sau hữu hạn bước chắc chắn sẽ chạm tới trường hợp cơ sở.

Hãy xem hai ví dụ kinh điển: tính giai thừa n! = n × (n - 1)! và tính tổng các chữ số của một số nguyên dương n:

#include <iostream>
using namespace std;

// Tính n! = 1 * 2 * ... * n bằng đệ quy
long long giaiThua(int n) {
    if (n <= 1) return 1;            // trường hợp cơ sở (điểm dừng)
    return n * giaiThua(n - 1);      // bước đệ quy thu nhỏ bài toán
}

// Tính tổng các chữ số của số nguyên không âm n
int tongChuSo(long long n) {
    if (n < 10) return (int)n;       // số có 1 chữ số
    return (int)(n % 10) + tongChuSo(n / 10);
}

int main() {
    cout << giaiThua(4) << "\n";      // 24
    cout << tongChuSo(2026) << "\n";  // 10 (2 + 0 + 2 + 6)
    return 0;
}

def giai_thua(n):
    """Tính n! = 1 * 2 * ... * n bằng đệ quy."""
    if n <= 1:
        return 1  # trường hợp cơ sở (điểm dừng)
    return n * giai_thua(n - 1)


def tong_chu_so(n):
    """Tính tổng các chữ số của số nguyên không âm n."""
    if n < 10:
        return n
    return (n % 10) + tong_chu_so(n // 10)


print(giai_thua(4))       # 24
print(tong_chu_so(2026))  # 10

Điều gì thực sự diễn ra trong bộ nhớ ngăn xếp (Call Stack)?

Nhiều bạn mới học thường thắc mắc: "Khi giaiThua(4) gọi giaiThua(3), biến n = 4 có bị ghi đè thành 3 không?". Câu trả lời là không, vì mỗi lần hàm được gọi, máy tính tạo ra một khung hàm (stack frame) hoàn toàn riêng biệt để giữ biến cục bộ n của lần gọi đó.

Hãy theo dõi từng bước khi gọi giaiThua(4):

Vì ngăn xếp phải giữ cùng lúc n khung hàm đang chờ trước khi chạm điểm dừng, nên dù hàm giaiThua(n) không khai báo mảng nào, độ phức tạp bộ nhớ của nó vẫn là O(n).

Bẫy tính lặp trong đệ quy phân nhánh và cách khắc phục bằng Đệ quy có nhớ

Với bài toán giai thừa, mỗi lần hàm chỉ gọi chính nó một lần, nên tổng số lần gọi là O(n). Nhưng với dãy số Fibonacci (F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2)), mỗi lần hàm gọi đệ quy hai lần:

• Để tính F(5), máy gọi F(4) và F(3).
• Trong F(4) lại gọi F(3) và F(2). Như vậy F(3) bị tính lại từ đầu hai lần, còn F(2) bị tính lại ba lần!
• Khi n tăng thêm 1, số lời gọi gần như nhân đôi, khiến độ phức tạp thời gian bùng nổ thành O(2ⁿ). Chỉ với n = 45, hàm đệ quy thường đã phải gọi hơn 3 tỷ lần.

Cách sửa rất đơn giản và đẹp mắt: ta tạo một mảng memo khởi tạo bằng -1. Trước khi gọi đệ quy tính fib(n), ta kiểm tra xem memo[n] đã có kết quả chưa; nếu có rồi thì trả về ngay lập tức, nếu chưa thì tính một lần rồi cất vào memo[n]. Kỹ thuật này gọi là đệ quy có nhớ (memoization):

#include <iostream>
#include <vector>
using namespace std;

int goiThuong = 0;
long long fibThuong(int n) {
    goiThuong++;
    if (n <= 1) return n;
    return fibThuong(n - 1) + fibThuong(n - 2);
}

int goiNho = 0;
long long fibNho(int n, vector<long long>& memo) {
    goiNho++;
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];  // đã tính rồi thì lấy ra dùng ngay
    memo[n] = fibNho(n - 1, memo) + fibNho(n - 2, memo);
    return memo[n];
}

int main() {
    vector<long long> memo10(11, -1);
    cout << fibThuong(10) << " " << goiThuong << "\n";       // 55 177
    cout << fibNho(10, memo10) << " " << goiNho << "\n";     // 55 19

    vector<long long> memo40(41, -1);
    cout << fibNho(40, memo40) << "\n";                      // 102334155
    return 0;
}

goi_thuong = 0


def fib_thuong(n):
    global goi_thuong
    goi_thuong += 1
    if n <= 1:
        return n
    return fib_thuong(n - 1) + fib_thuong(n - 2)


goi_nho = 0


def fib_nho(n, memo):
    global goi_nho
    goi_nho += 1
    if n <= 1:
        return n
    if memo[n] != -1:
        return memo[n]
    memo[n] = fib_nho(n - 1, memo) + fib_nho(n - 2, memo)
    return memo[n]


memo10 = [-1] * 11
print(fib_thuong(10), goi_thuong)   # 55 177
print(fib_nho(10, memo10), goi_nho) # 55 19

memo40 = [-1] * 41
print(fib_nho(40, memo40))          # 102334155

Hãy nhìn kết quả in ra từ chương trình trên:

• Với n = 10: hàm fibThuong(10) phải gọi đệ quy 177 lần, trong khi fibNho(10) chỉ gọi đúng 19 lần.
• Với n = 40: hàm fibNho(40) trả về ngay 102334155 chỉ sau 79 lần gọi hàm (độ phức tạp giảm từ O(2ⁿ) xuống đúng O(n)). Đây cũng chính là ý tưởng cốt lõi của quy hoạch động từ trên xuống (Top-down Dynamic Programming).

Khi nào nên dùng đệ quy, khi nào nên dùng vòng lặp?

Lỗi hay gặp khi viết hàm đệ quy

Luyện ngay trên Big-O Coding

Thực hành ngay tư duy chia nhỏ bài toán và đệ quy qua các bài tập dưới đây trên hệ thống Big-O Coding:

Câu hỏi thường gặp

Nguồn tham khảo

• MIT 6.006: Recursion & Induction
• Python Documentation: sys.setrecursionlimit
• cppreference: Function call expressions