Bài 14.4: Tối ưu hóa đệ quy trong C++

Đệ quy là một công cụ mạnh mẽ trong lập trình, cho phép chúng ta giải quyết các vấn đề phức tạp bằng cách chia nhỏ chúng thành các bài toán con tương tự nhỏ hơn. Nó thường mang lại sự thanh lịch và dễ đọc cho code, đặc biệt khi ánh xạ trực tiếp các định nghĩa toán học hoặc cấu trúc dữ liệu đệ quy.

Tuy nhiên, đệ quy cũng có mặt trái của nó. Việc gọi hàm liên tục có thể dẫn đến chi phí hiệu năng đáng kể do quản lý stack (ngăn xếp) cho mỗi lần gọi. Quan trọng hơn, với các bài toán có các bài toán con trùng lặp hoặc độ sâu đệ quy lớn, đệ quy "ngây thơ" (naive recursion) có thể trở nên cực kỳ chậm và thậm chí gây ra lỗi Stack Overflow do bộ nhớ stack bị cạn kiệt.

May mắn thay, có những kỹ thuật khéo léo mà chúng ta có thể áp dụng để "thuần hóa" và tối ưu hóa các hàm đệ quy trong C++, biến chúng thành những giải pháp hiệu quả hơn nhiều. Trong bài viết này, chúng ta sẽ cùng nhau khám phá những bí mật đằng sau việc tối ưu hóa đệ quy.

1. Vấn đề của Đệ quy "Ngây thơ": Ví dụ Fibonacci

Hãy bắt đầu với một ví dụ kinh điển cho thấy sự kém hiệu quả của đệ quy "ngây thơ": tính số Fibonacci thứ n. Dãy Fibonacci được định nghĩa như sau: F(0) = 0, F(1) = 1, và F(n) = F(n-1) + F(n-2) cho n > 1.

Phiên bản đệ quy trực tiếp của định nghĩa này trong C++ trông khá đơn giản:

#include <iostream>

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

Tại sao hàm này lại kém hiệu quả, đặc biệt với các giá trị n lớn? Vấn đề nằm ở việc nó tính toán cùng một giá trị nhiều lần. Ví dụ, để tính fibonacci_naive(5), chúng ta cần tính fibonacci_naive(4) và fibonacci_naive(3). Để tính fibonacci_naive(4), chúng ta cần fibonacci_naive(3) và fibonacci_naive(2). Bạn thấy không? fibonacci_naive(3) bị tính lặp lại! Khi n tăng lên, số lần tính toán lại các bài toán con trùng lặp này tăng theo cấp số nhân, dẫn đến thời gian chạy bùng nổ.

Đây là một ví dụ điển hình về vấn đề Các Bài toán con Trùng lặp (Overlapping Subproblems), một dấu hiệu cho thấy chúng ta có thể áp dụng các kỹ thuật tối ưu hóa như Memoization hoặc Quy hoạch động.

2. Kỹ thuật Tối ưu hóa 1: Tối ưu hóa Đệ quy Đuôi (Tail Call Optimization - TCO)

Đệ quy đuôi là một trường hợp đặc biệt của đệ quy mà lệnh gọi đệ quy là hành động cuối cùng mà hàm thực hiện trước khi trả về giá trị. Không có phép tính nào khác được thực hiện sau khi lệnh gọi đệ quy trả về.

Tại sao điều này lại quan trọng? Một số trình biên dịch hiện đại (như GCC và Clang với mức tối ưu hóa phù hợp như -O2, -O3) có thể nhận diện dạng đệ quy đuôi này và biến đổi nó thành một vòng lặp thông thường. Quá trình này được gọi là Tail Call Optimization (TCO). Khi TCO xảy ra, lệnh gọi đệ quy không còn tạo ra một stack frame mới nữa, loại bỏ đáng kể chi phí gọi hàm và quan trọng nhất là ngăn chặn lỗi Stack Overflow do đệ quy sâu.

Tuy nhiên, cần lưu ý rằng tiêu chuẩn C++ không bắt buộc trình biên dịch phải thực hiện TCO. Sự có mặt và hiệu quả của TCO phụ thuộc vào trình biên dịch và các tùy chọn biên dịch bạn sử dụng.

Hãy xem một ví dụ về tính giai thừa (n!) để hiểu rõ hơn.

Phiên bản đệ quy không phải đệ quy đuôi:

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

Trong hàm gt_k_duoi, lệnh gọi gt_k_duoi(n-1) không phải là hành động cuối cùng. Kết quả của nó còn phải được nhân với n trước khi hàm hiện tại trả về. Do đó, đây không phải là đệ quy đuôi.

Phiên bản đệ quy đuôi: Để biến đổi thành đệ quy đuôi, chúng ta thường cần một tham số bổ sung, gọi là tham số tích lũy (accumulator), để mang theo kết quả trung gian.

long long gt_duoi_phu(int n, long long t) {
    if (n == 0) {
        return t;
    }
    return gt_duoi_phu(n - 1, n * t);
}

long long gt_duoi(int n) {
    if (n < 0) return -1;
    return gt_duoi_phu(n, 1);
}

Trong gt_duoi_phu, hành động cuối cùng là lệnh gọi gt_duoi_phu(n - 1, n * t). Kết quả của lệnh gọi này được trả về ngay lập tức bởi hàm hiện tại mà không cần thực hiện thêm bất kỳ phép tính nào. Đây chính là dạng đệ quy đuôi. Nếu trình biên dịch hỗ trợ TCO, hàm này sẽ hiệu quả như một vòng lặp.

3. Kỹ thuật Tối ưu hóa 2: Ghi nhớ (Memoization)

Trở lại với ví dụ Fibonacci kém hiệu quả. Vấn đề cốt lõi là các bài toán con trùng lặp. Kỹ thuật Ghi nhớ (Memoization) giải quyết vấn đề này bằng cách lưu trữ kết quả của các bài toán con đã được giải quyết. Trước khi tính toán kết quả cho một đầu vào cụ thể, hàm sẽ kiểm tra xem kết quả đó đã được tính và lưu trữ trước đó chưa. Nếu có, nó chỉ cần trả về kết quả đã lưu thay vì tính toán lại.

Kỹ thuật này biến thời gian chạy của hàm Fibonacci từ O(2^n) (cực kỳ tệ) thành O(n) (tuyến tính, rất tốt), vì mỗi giá trị Fibonacci chỉ cần được tính toán một lần.

Để triển khai Memoization trong C++, chúng ta có thể sử dụng một mảng (vector) hoặc bản đồ (map) để lưu trữ kết quả đã tính. vector thường hiệu quả hơn nếu các đầu vào là các số nguyên không âm liên tiếp bắt đầu từ 0, như trong trường hợp Fibonacci.

#include <vector>
#include <iostream>

long long fib_ghinho_phu(int n, vector<long long>& bang) {
    if (n <= 1) {
        return n;
    }
    if (bang[n] != -1) {
        return bang[n];
    }
    bang[n] = fib_ghinho_phu(n - 1, bang) + fib_ghinho_phu(n - 2, bang);
    return bang[n];
}

long long fib_ghinho(int n) {
    if (n < 0) return -1;
    vector<long long> bang(n + 1, -1);
    return fib_ghinho_phu(n, bang);
}

Trong code này, chúng ta sử dụng một vector<long long> bang có kích thước n + 1 để lưu trữ kết quả F(i) tại chỉ số i. Chúng ta khởi tạo tất cả các phần tử bằng -1 để đánh dấu rằng chưa có giá trị nào được tính (giả sử giá trị Fibonacci không âm). Hàm fib_ghinho_phu kiểm tra bang[n]. Nếu nó không phải -1, tức là đã tính rồi, nó trả về giá trị đó. Nếu không, nó tính toán đệ quy, lưu kết quả vào bang[n], rồi trả về.

Memoization không giải quyết được vấn đề Stack Overflow cho đệ quy sâu, vì các lệnh gọi đệ quy vẫn được đẩy vào stack. Tuy nhiên, nó giải quyết triệt để vấn đề tính toán lặp lại, cải thiện thời gian chạy một cách ngoạn mục cho các bài toán có bài toán con trùng lặp.

4. Kỹ thuật Tối ưu hóa 3: Chuyển đổi sang Lặp (Iteration)

Đôi khi, cách tốt nhất để tối ưu hóa một hàm đệ quy là loại bỏ hoàn toàn đệ quy và viết lại nó dưới dạng lặp (sử dụng vòng lặp for, while). Kỹ thuật này thường được gọi là Quy hoạch động từ dưới lên (Bottom-Up Dynamic Programming).

Thay vì bắt đầu từ bài toán lớn (F(n)) và đệ quy xuống bài toán nhỏ (F(n-1), F(n-2)), chúng ta bắt đầu từ các trường hợp cơ bản đã biết (F(0), F(1)) và xây dựng dần lên kết quả cuối cùng (F(n)).

Cách tiếp cận lặp mang lại hiệu quả cao nhất vì nó loại bỏ hoàn toàn chi phí gọi hàm đệ quy và quản lý stack.

Với ví dụ Fibonacci, chúng ta có thể tính toán F(i) cho i từ 2 đến n, sử dụng các giá trị F(i-1) và F(i-2) đã được tính toán trước đó.

#include <iostream>
#include <vector>

long long fib_lap(int n) {
    if (n <= 1) {
        return n;
    }
    vector<long long> fib(n + 1);
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; ++i) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
}

long long fib_lap_toi_uu(int n) {
    if (n <= 1) {
        return n;
    }
    long long a = 0;
    long long b = 1;
    long long kq = 0;

    for (int i = 2; i <= n; ++i) {
        kq = a + b;
        a = b;
        b = kq;
    }
    return kq;
}

Phiên bản fib_lap sử dụng một vector để lưu trữ tất cả các giá trị từ F(0) đến F(n). Phiên bản fib_lap_toi_uu còn tốt hơn nữa về mặt bộ nhớ; nó chỉ cần lưu trữ hai giá trị trước đó (a và b) để tính giá trị hiện tại, giảm bộ nhớ sử dụng xuống O(1) (không đổi theo n).

Việc chuyển đổi sang lặp thường là lựa chọn tối ưu nhất về cả thời gian và bộ nhớ khi có thể, đặc biệt cho các bài toán Quy hoạch động mà thứ tự tính toán các bài toán con có thể được xác định từ dưới lên.

Tổng kết các kỹ thuật

Chúng ta đã xem xét ba kỹ thuật chính để tối ưu hóa đệ quy:

Tail Call Optimization (TCO): Biến đổi đệ quy đuôi thành vòng lặp (phụ thuộc trình biên dịch). Tốt cho việc tiết kiệm stack space và tránh Stack Overflow.
Memoization: Lưu trữ kết quả của các bài toán con đã giải quyết để tránh tính toán lặp lại. Tốt cho việc cải thiện thời gian chạy trên các bài toán có bài toán con trùng lặp, nhưng vẫn có thể bị giới hạn bởi độ sâu stack.
Iteration (Quy hoạch động từ dưới lên): Viết lại hàm đệ quy bằng vòng lặp. Thường là cách hiệu quả nhất về cả thời gian và bộ nhớ, loại bỏ hoàn toàn chi phí đệ quy.

Khi đối mặt với một bài toán đệ quy cần tối ưu, bạn nên xem xét:

Bài toán có các bài toán con trùng lặp không? -> Cân nhắc Memoization hoặc Iteration.
Có thể biến đổi thành đệ quy đuôi không? -> Cân nhắc TCO (nhưng hãy nhớ sự phụ thuộc vào trình biên dịch).
Có thể viết lại bằng một vòng lặp từ dưới lên không? -> Thường là lựa chọn tốt nhất nếu khả thi.

Bài tập ví dụ: C++ Bài 14.B1: Chuẩn bị cho kỳ thi

Chuẩn bị cho kỳ thi

FullHouse Dev đang chuẩn bị cho một kỳ thi sắp tới. Tuy nhiên, thay vì ôn tập, FullHouse Dev lại bắt đầu xem Mùa 1 của một bộ phim. Mùa 1 có N tập, và mỗi tập dài K phút. Kỳ thi sẽ bắt đầu sau đúng M phút nữa.

Hãy xác định xem FullHouse Dev có thể xem hết Mùa 1 trước khi kỳ thi bắt đầu hay không.

INPUT FORMAT

Dòng đầu tiên chứa số nguyên T - số lượng bộ test.
Mỗi bộ test gồm một dòng chứa 3 số nguyên cách nhau bởi dấu cách: M, N và K.

OUTPUT FORMAT

Với mỗi bộ test, in ra "YES" nếu có thể xem hết Mùa 1 trước khi kỳ thi bắt đầu, hoặc "NO" nếu không thể.

CONSTRAINTS

\(1 ≤ T ≤ 10^4\)
\(1 ≤ M ≤ 10^9\)
\(1 ≤ N, K ≤ 10^4\)

Ví dụ

Input

Output

NO
YES
NO

Giải thích:

Test 1: Tập phim duy nhất dài 10 phút, và kỳ thi bắt đầu sau 10 phút. Vì vậy, FullHouse Dev sẽ không thể xem hết trước khi kỳ thi bắt đầu.
Test 2: Có hai tập phim, mỗi tập dài 10 phút. Tổng thời gian xem là 10 + 10 = 20 phút. Vì kỳ thi bắt đầu sau 25 phút, nên FullHouse Dev có thể xem hết trước khi kỳ thi bắt đầu.
Test 3: Có hai tập phim, mỗi tập dài 10 phút. Tổng thời gian xem là 10 + 10 = 20 phút. Vì kỳ thi bắt đầu sau 15 phút, nên FullHouse Dev sẽ không thể xem hết trước khi kỳ thi bắt đầu. Chào bạn, đây là hướng dẫn giải bài tập "Chuẩn bị cho kỳ thi" bằng C++ theo yêu cầu:

Bài toán này khá đơn giản, yêu cầu chúng ta kiểm tra xem tổng thời gian cần để xem hết các tập phim có nhỏ hơn hoặc bằng thời gian còn lại trước khi kỳ thi bắt đầu hay không.

Xác định tổng thời gian cần thiết:
- Bạn có N tập phim.
- Mỗi tập dài K phút.
- Tổng thời gian cần để xem hết Mùa 1 là: N nhân K.
Xác định điều kiện để xem xong:
- Kỳ thi bắt đầu sau M phút.
- Để xem hết Mùa 1 trước khi kỳ thi bắt đầu (hoặc đúng lúc kỳ thi bắt đầu), tổng thời gian xem phải nhỏ hơn hoặc bằng thời gian còn lại.
- Điều kiện là: (Tổng thời gian xem) <= M.
- Hay cụ thể hơn: (N * K) <= M.
Kiểm tra và đưa ra kết quả:
- Nếu điều kiện (N * K) <= M đúng, in ra "YES".
- Nếu điều kiện (N * K) <= M sai, in ra "NO".
Lặp lại cho các bộ test:
- Đề bài cho T bộ test. Bạn cần đọc giá trị T đầu tiên.
- Sau đó, sử dụng một vòng lặp (ví dụ: for hoặc while) chạy T lần.
- Bên trong mỗi lần lặp, đọc 3 số M, N, K và thực hiện bước 1, 2, 3.
Lưu ý về kiểu dữ liệu:
- Các giá trị M, N, K có thể lên tới 10^9 (đối với M) và 10^4 (đối với N, K).
- Tích N K có thể lên tới 10^4 10^4 = 10^8.
- Các kiểu dữ liệu số nguyên cơ bản trong C++ (như int) thường có phạm vi đủ lớn để lưu trữ M (lên tới 210^9) và tích NK (lên tới 10^8). Tuy nhiên, để đảm bảo an toàn với giá trị M lớn, bạn nên sử dụng kiểu dữ liệu long long cho biến lưu M và có thể cả cho tích NK trước khi so sánh với M, mặc dù với ràng buộc N, K <= 10^4 thì int cho N, K, và NK vẫn đủ. Sử dụng long long cho M và kết quả của N*K là cách an toàn nhất.
Cấu trúc chương trình C++:
- Bao gồm thư viện iostream cho nhập/xuất.
- Có thể sử dụng cin và cout để nhập và xuất dữ liệu.
- Đối với các bài tập có T bộ test và cần tốc độ I/O, bạn có thể thêm dòng sau ở đầu hàm main để tối ưu I/O của C++: ios_base::sync_with_stdio(false); cin.tie(NULL);.
- Đọc T.
- Sử dụng vòng lặp while (T--) hoặc for (int i = 0; i < T; ++i) để xử lý từng bộ test.
- Bên trong vòng lặp:
  - Khai báo các biến (ví dụ: long long M; int N, K;).
  - Đọc giá trị M, N, K.
  - Tính tích (long long)N * K (ép kiểu sang long long để tránh tràn số nếu M lớn và N, K đủ lớn khiến tích vượt quá int, mặc dù với ràng buộc hiện tại thì không xảy ra).
  - So sánh tích này với M.
  - In ra "YES" hoặc "NO" theo sau là ký tự xuống dòng (endl hoặc '\n').

#include <iostream>

void giai_quyet() {
    long long m; // thoi gian ky thi bat dau (phut)
    int n, k;    // so tap phim, thoi luong moi tap (phut)
    cin >> m >> n >> k;

    long long tg = (long long)n * k; // tong thoi gian can xem

    // Can xem xong TRUOC KHI ky thi bat dau
    if (tg < m) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

int main() {
    // Toi uu toc do nhap/xuat
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t; // so luong bo test
    cin >> t;
    while (t--) {
        giai_quyet();
    }
    return 0;
}

Output của code trên với ví dụ đã cho:

NO
YES
NO

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.