1. Đệ quy trong C++

1.1 Khái niệm

Đệ quy là kỹ thuật lập trình mà trong đó một hàm tự gọi lại chính nó để giải quyết bài toán.

Ý tưởng cơ bản:

• Bài toán lớn được chia thành các bài toán con cùng dạng nhưng nhỏ hơn.
• Quá trình gọi lại tiếp tục cho đến khi gặp một trường hợp đơn giản đã biết kết quả.

Có thể hình dung đệ quy giống như hai chiếc gương đặt đối diện nhau. Mỗi hình ảnh lại chứa hình ảnh nhỏ hơn của chính nó, lặp đi lặp lại cho đến khi rất nhỏ.

1.2 Cấu trúc tổng quát

void deQuy(int thamSo) {

    // Điều kiện dừng
    if (dieuKienDung) {
        return;
    }

    // Bước đệ quy
    deQuy(thamSoMoi);
}

1.3 Thành phần của đệ quy

Ví dụ sai:

int tinhTongSai(int n) {
    return n + tinhTongSai(n - 1);
}

Ví dụ đúng:

int tinhTongDung(int n) {
    if (n == 1) return 1;
    return n + tinhTongDung(n - 1);
}

Stack Overflow là gì?

Mỗi lần gọi hàm, chương trình phải lưu trạng thái hiện tại vào bộ nhớ Stack.

Nếu hàm liên tục gọi lại chính nó mà không dừng, bộ nhớ Stack sẽ bị đầy và chương trình bị lỗi Stack Overflow.

1.4 Ví dụ: Tính giai thừa bằng đệ quy

Bài toán:

Tính:

~n! = n \times (n-1) \times (n-2) \times \dots \times 1~

Với:

~0! = 1~

Công thức truy hồi:

~n! = n \times (n-1)!~

#include <iostream>
using namespace std;

long long tinhGiaiThua(int n) {
    if (n == 0) return 1;
    return n * tinhGiaiThua(n - 1);
}

int main() {
    cout << tinhGiaiThua(5);
}

Kết quả:

120

1.5 Call Stack hoạt động như thế nào?

Khi gọi:

tinhGiaiThua(4);

Máy tính thực hiện:

tinhGiaiThua(4)
    -> tinhGiaiThua(3)
        -> tinhGiaiThua(2)
            -> tinhGiaiThua(1)
                -> tinhGiaiThua(0)

Tại n = 0, hàm dừng và trả về:

1

Sau đó kết quả được truyền ngược lại:

1
1 × 1 = 1
2 × 1 = 2
3 × 2 = 6
4 × 6 = 24

Kết quả cuối cùng:

24

1.6 Các bước xây dựng hàm đệ quy

Ví dụ với giai thừa:

• Base Case: ~0! = 1~
• Công thức: ~n! = n \times (n-1)!~
• Mỗi lần gọi giảm ~n~ đi 1.

2. So sánh đệ quy và vòng lặp

Tính tổng từ 1 đến n bằng vòng lặp

int tongVongLap(int n) {
    int tong = 0;

    for (int i = 1; i <= n; i++) {
        tong += i;
    }

    return tong;
}

Tính tổng từ 1 đến n bằng đệ quy

int tongDeQuy(int n) {
    if (n == 1) return 1;
    return n + tongDeQuy(n - 1);
}

So sánh

3. Khi nào nên dùng đệ quy?

Nên dùng

• Giai thừa.
• Fibonacci.
• Duyệt cây.
• Duyệt đồ thị.
• Backtracking.
• Chia để trị.

Không nên dùng

• Dữ liệu rất lớn.
• Độ sâu đệ quy quá lớn.
• Bài toán tuần tự đơn giản có thể dùng vòng lặp.