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;
    }
    // Tính F(n-1) và F(n-2)
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2);
}

// Ví dụ sử dụng (chỉ minh họa, không cần chạy)
/*
int main() {
    cout << "Fib(10): " << fibonacci_naive(10) << endl; // Nhanh
    cout << "Fib(20): " << fibonacci_naive(20) << endl; // Tạm được
    cout << "Fib(40): " << fibonacci_naive(40) << endl; // Cực kỳ chậm!
    return 0;
}
*/

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 factorial_non_tail(int n) {
    if (n == 0) {
        return 1;
    }
    // Phép nhân n * ... xảy ra SAU khi lệnh gọi đệ quy trả về
    return n * factorial_non_tail(n - 1);
}

Trong hàm factorial_non_tail, lệnh gọi factorial_non_tail(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.

// Hàm trợ giúp là hàm đệ quy đuôi
long long factorial_tail_recursive_helper(int n, long long accumulator) {
    if (n == 0) {
        return accumulator;
    }
    // Hành động CUỐI CÙNG là lệnh gọi đệ quy, không có phép tính nào sau đó
    return factorial_tail_recursive_helper(n - 1, n * accumulator);
}

// Hàm wrapper để khởi tạo giá trị tích lũy
long long factorial_tail(int n) {
    if (n < 0) return -1; // Xử lý đầu vào không hợp lệ
    return factorial_tail_recursive_helper(n, 1); // Giai thừa của 0 là 1, bắt đầu với accumulator = 1
}

// Ví dụ sử dụng
/*
int main() {
    cout << "Factorial(5): " << factorial_tail(5) << endl; // Output: 120
    cout << "Factorial(10): " << factorial_tail(10) << endl; // Output: 3628800
    // Với TCO, có thể tính giai thừa của số lớn hơn mà không sợ Stack Overflow
    // cout << "Factorial(100000): " << factorial_tail(100000) << endl;
    return 0;
}
*/

Trong factorial_tail_recursive_helper, hành động cuối cùng là lệnh gọi factorial_tail_recursive_helper(n - 1, n * accumulator). 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> // Cần include cho vector
#include <iostream> // Cho ví dụ in ra

// Hàm trợ giúp có áp dụng memoization
long long fibonacci_memo_helper(int n, vector<long long>& memo) {
    if (n <= 1) {
        return n;
    }
    // Kiểm tra xem kết quả cho n đã được tính chưa
    if (memo[n] != -1) { // Giả sử -1 là giá trị sentinel (chưa tính)
        return memo[n];
    }
    // Nếu chưa, tính toán, lưu trữ và trả về
    // Lưu ý: Lệnh gọi đệ quy vẫn tạo stack frame, nên vẫn có giới hạn độ sâu stack
    memo[n] = fibonacci_memo_helper(n - 1, memo) + fibonacci_memo_helper(n - 2, memo);
    return memo[n];
}

// Hàm wrapper để khởi tạo bảng ghi nhớ
long long fibonacci_memoized(int n) {
    if (n < 0) return -1; // Xử lý đầu vào không hợp lệ
    // Khởi tạo vector với kích thước n+1 và giá trị -1 (chưa tính)
    vector<long long> memo(n + 1, -1);
    return fibonacci_memo_helper(n, memo);
}

// Ví dụ sử dụng
/*
int main() {
    cout << "Fib(10): " << fibonacci_memoized(10) << endl; // Nhanh
    cout << "Fib(40): " << fibonacci_memoized(40) << endl; // Rất nhanh!
    cout << "Fib(90): " << fibonacci_memoized(90) << endl; // Rất nhanh (nếu long long đủ lớn)
    return 0;
}
*/

Trong code này, chúng ta sử dụng một vector<long long> memo 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 fibonacci_memo_helper kiểm tra memo[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 memo[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> // Cho ví dụ in ra
#include <vector> // Có thể dùng vector, hoặc tối ưu không gian

long long fibonacci_iterative(int n) {
    if (n <= 1) {
        return n;
    }
    // Sử dụng vector để lưu trữ kết quả trung gian (O(n) bộ nhớ)
    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];
}

// Phiên bản lặp tối ưu hóa không gian (O(1) bộ nhớ)
long long fibonacci_iterative_optimized(int n) {
    if (n <= 1) {
        return n;
    }
    long long a = 0; // Tương ứng với F(i-2) trong bước hiện tại
    long long b = 1; // Tương ứng với F(i-1) trong bước hiện tại
    long long result = 0;

    for (int i = 2; i <= n; ++i) {
        result = a + b; // Tính F(i) = F(i-1) + F(i-2)
        a = b;          // Chuẩn bị a cho bước tiếp theo (a trở thành F(i-1))
        b = result;     // Chuẩn bị b cho bước tiếp theo (b trở thành F(i))
    }
    return result; // Kết quả cuối cùng là F(n)
}

// Ví dụ sử dụng
/*
int main() {
    cout << "Fib(10): " << fibonacci_iterative_optimized(10) << endl; // Cực nhanh
    cout << "Fib(40): " << fibonacci_iterative_optimized(40) << endl; // Cực nhanh
    cout << "Fib(90): " << fibonacci_iterative_optimized(90) << endl; // Cực nhanh
    return 0;
}
*/

Phiên bản fibonacci_iterative 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 fibonacci_iterative_optimized 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').

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

Comments

There are no comments at the moment.