Bài 14.3: Các bài toán đệ quy cơ bản trong C++

Chào mừng trở lại với chuỗi bài viết về C++! Hôm nay, chúng ta sẽ bước vào một khái niệm vô cùng thú vị và mạnh mẽ trong lập trình: Đệ quy (Recursion).

Đệ quy là một kỹ thuật mà một hàm tự gọi chính nó để giải quyết một vấn đề. Thoạt nghe có vẻ khó hiểu hoặc thậm chí là "tự sướng", nhưng khi áp dụng đúng cách, đệ quy có thể giúp chúng ta viết mã thanh lịch hơn, ngắn gọn hơn và phản ánh trực tiếp định nghĩa toán học của nhiều bài toán. Tuy nhiên, nó cũng đòi hỏi sự cẩn trọng để tránh những lỗi thường gặp như lặp vô hạn (infinite recursion).

Hãy cùng khám phá xem đệ quy hoạt động như thế nào và áp dụng nó vào một số bài toán cơ bản nhé!

Đệ quy là gì? Nguyên lý hoạt động

Ý tưởng cốt lõi của đệ quy là chia nhỏ một bài toán lớn thành một hoặc nhiều bài toán nhỏ hơn, tương tự với bài toán ban đầu, cho đến khi bài toán trở nên đủ đơn giản để có thể giải quyết trực tiếp mà không cần chia nhỏ thêm nữa.

Để một hàm đệ quy hoạt động chính xác, nó bắt buộc phải có hai thành phần chính:

Trường hợp cơ sở (Base Case): Đây là điều kiện dừng của đệ quy. Khi đạt đến trường hợp cơ sở, hàm sẽ trả về một giá trị trực tiếp mà không gọi lại chính nó. Đây là yếu tố quan trọng nhất để ngăn chặn vòng lặp đệ quy vô hạn. Hãy nghĩ về nó như điểm dừng cuối cùng trong chuỗi các lời gọi hàm.
Bước đệ quy (Recursive Step): Đây là phần mà hàm gọi lại chính nó, nhưng với một phiên bản nhỏ hơn hoặc đơn giản hơn của bài toán ban đầu. Mỗi bước đệ quy phải tiến gần hơn đến trường hợp cơ sở. Nếu không, bạn sẽ rơi vào bẫy đệ quy vô hạn.

Sự kết hợp của hai thành phần này tạo nên "ma thuật" của đệ quy. Bài toán lớn được chia nhỏ dần cho đến khi đạt đến trường hợp đơn giản nhất (cơ sở), sau đó các kết quả từ các bài toán nhỏ hơn sẽ được kết hợp lại để giải quyết bài toán ban đầu.

Các bài toán đệ quy cơ bản

Chúng ta sẽ đi qua một vài ví dụ điển hình để hiểu rõ hơn cách áp dụng đệ quy trong C++.

Ví dụ 1: Tính Giai thừa (Factorial)

Bài toán tính giai thừa của một số nguyên dương n (ký hiệu n!) là một trong những ví dụ kinh điển nhất về đệ quy. Định nghĩa toán học của giai thừa là:

0! = 1 (Trường hợp cơ sở)
n! = n * (n-1)! với n > 0 (Bước đệ quy)

Dễ thấy định nghĩa này đã "mách nước" cho chúng ta cách viết hàm đệ quy rồi!

Hãy cùng xem mã C++ cho hàm tính giai thừa đệ quy:

#include <iostream>

long long factorial(int n) {
    // Trường hợp cơ sở: Khi n = 0, trả về 1
    if (n == 0) {
        return 1;
    }
    // Bước đệ quy: n! = n * (n-1)!
    else {
        return n * factorial(n - 1);
    }
}

int main() {
    int num = 5;
    cout << "Giai thua cua " << num << " la: " << factorial(num) << endl; // Output: 120
    return 0;
}

Giải thích code:

Hàm factorial(int n) nhận vào một số nguyên n.
Dòng if (n == 0) kiểm tra trường hợp cơ sở. Nếu n bằng 0, hàm dừng đệ quy và trả về 1.
Phần else xử lý bước đệ quy. Hàm trả về kết quả của n nhân với lời gọi đệ quy factorial(n - 1). Mỗi lần gọi đệ quy, giá trị của n giảm đi 1, đảm bảo rằng cuối cùng nó sẽ đạt đến trường hợp cơ sở n == 0.
Hàm main chỉ đơn giản gọi hàm factorial với một giá trị cụ thể và in kết quả.

Hãy thử theo dõi lời gọi factorial(3):

factorial(3) gọi 3 * factorial(2)
factorial(2) gọi 2 * factorial(1)
factorial(1) gọi 1 * factorial(0)
factorial(0) trả về 1 (Trường hợp cơ sở)
factorial(1) nhận 1 và trả về 1 * 1 = 1
factorial(2) nhận 1 và trả về 2 * 1 = 2
factorial(3) nhận 2 và trả về 3 * 2 = 6. Và 3! thực sự bằng 6. Tuyệt vời!

Ví dụ 2: Dãy số Fibonacci

Dãy số Fibonacci là một dãy số bắt đầu bằng 0 và 1, trong đó mỗi số tiếp theo là tổng của hai số đứng trước nó. Các số đầu tiên của dãy là: 0, 1, 1, 2, 3, 5, 8, 13, ...

Định nghĩa toán học:

F(0) = 0 (Trường hợp cơ sở 1)
F(1) = 1 (Trường hợp cơ sở 2)
F(n) = F(n-1) + F(n-2) với n > 1 (Bước đệ quy)

Lại một bài toán nữa có định nghĩa "thuận lợi" cho đệ quy.

Mã C++ cho hàm tính số Fibonacci thứ n bằng đệ quy:

#include <iostream>

int fibonacci(int n) {
    // Trường hợp cơ sở: Khi n = 0 hoặc n = 1
    if (n <= 1) {
        return n;
    }
    // Bước đệ quy: F(n) = F(n-1) + F(n-2)
    else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main() {
    int num = 6;
    cout << "So Fibonacci thu " << num << " la: " << fibonacci(num) << endl; // Output: 8 (0, 1, 1, 2, 3, 5, 8)
    return 0;
}

Giải thích code:

Hàm fibonacci(int n) tính số Fibonacci thứ n.
Dòng if (n <= 1) xử lý hai trường hợp cơ sở: F(0) và F(1). Cả hai đều trả về chính n.
Phần else thực hiện bước đệ quy, trả về tổng của hai lời gọi đệ quy: fibonacci(n - 1) và fibonacci(n - 2). Mỗi lời gọi này giải quyết một bài toán con nhỏ hơn.
Hàm main tương tự, gọi hàm fibonacci và in kết quả.

Lưu ý quan trọng: Cách triển khai Fibonacci bằng đệ quy trực tiếp này rất kém hiệu quả với các giá trị n lớn, bởi vì cùng một giá trị Fibonacci sẽ được tính đi tính lại nhiều lần (ví dụ, để tính F(5), bạn cần F(4) và F(3); để tính F(4), bạn cần F(3) và F(2) - F(3) bị tính hai lần). Đây là một minh họa cho thấy đệ quy không phải lúc nào cũng là giải pháp tối ưu về mặt hiệu năng, và các phương pháp khác như lặp hoặc quy hoạch động thường được ưu tiên hơn cho bài toán này khi n lớn. Tuy nhiên, về mặt khái niệm đệ quy, đây là một ví dụ tuyệt vời.

Ví dụ 3: Tính tổng các chữ số của một số

Bài toán này yêu cầu tính tổng của tất cả các chữ số trong một số nguyên không âm. Ví dụ: tổng các chữ số của 123 là 1 + 2 + 3 = 6.

Cách tiếp cận đệ quy:

Trường hợp cơ sở: Nếu số chỉ có một chữ số (nhỏ hơn 10), tổng chính là số đó.
Bước đệ quy: Tổng các chữ số của một số n bằng chữ số cuối cùng của nó (n % 10) cộng với tổng các chữ số của phần còn lại của số (n / 10).

Mã C++ cho hàm tính tổng chữ số bằng đệ quy:

#include <iostream>

int sumDigits(int n) {
    // Trường hợp cơ sở: Nếu số chỉ có một chữ số
    if (n < 10) {
        return n;
    }
    // Bước đệ quy: Chữ số cuối + tổng chữ số của phần còn lại
    else {
        return (n % 10) + sumDigits(n / 10);
    }
}

int main() {
    int num = 456;
    cout << "Tong cac chu so cua " << num << " la: " << sumDigits(num) << endl; // Output: 15
    return 0;
}

Giải thích code:

Hàm sumDigits(int n) tính tổng các chữ số của n.
Dòng if (n < 10) kiểm tra trường hợp cơ sở. Nếu n nhỏ hơn 10, nó chỉ có một chữ số, nên hàm trả về chính n.
Phần else thực hiện bước đệ quy.
- n % 10 lấy chữ số cuối cùng của n.
- n / 10 lấy phần còn lại của số sau khi bỏ đi chữ số cuối cùng (ví dụ: 456 / 10 = 45).
- Hàm cộng chữ số cuối cùng với kết quả của lời gọi đệ quy trên phần còn lại của số. Mỗi lần gọi đệ quy, số n giảm đi về độ lớn, đảm bảo cuối cùng nó sẽ nhỏ hơn 10 (hoặc âm nếu ban đầu n là âm, nhưng ví dụ này tập trung vào số không âm).
Hàm main minh họa cách sử dụng.

Ví dụ 4: Tính lũy thừa (Power)

Tính giá trị của x mũ n (x^n) với n là số nguyên không âm.

Định nghĩa toán học:

x^0 = 1 (Trường hợp cơ sở)
x^n = x * x^(n-1) với n > 0 (Bước đệ quy)

Mã C++ cho hàm tính lũy thừa bằng đệ quy:

#include <iostream>

double power(double base, int exp) {
    // Trường hợp cơ sở: Bất kỳ số nào mũ 0 đều bằng 1
    if (exp == 0) {
        return 1.0;
    }
    // Bước đệ quy: x^n = x * x^(n-1)
    else {
        return base * power(base, exp - 1);
    }
}

int main() {
    double base = 2.0;
    int exp = 5;
    cout << base << "^" << exp << " = " << power(base, exp) << endl; // Output: 32
    return 0;
}

Giải thích code:

Hàm power(double base, int exp) tính base mũ exp.
Dòng if (exp == 0) kiểm tra trường hợp cơ sở. Nếu số mũ exp là 0, hàm trả về 1.0.
Phần else thực hiện bước đệ quy. Hàm trả về base nhân với kết quả của lời gọi đệ quy power(base, exp - 1). Mỗi lần gọi đệ quy, số mũ exp giảm đi 1, dần tiến về trường hợp cơ sở.
Hàm main minh họa cách sử dụng.

Qua các ví dụ này, hy vọng bạn đã thấy được sức mạnh và sự thanh lịch của đệ quy trong việc giải quyết các bài toán có cấu trúc lặp lại.

Những điều cần lưu ý khi sử dụng đệ quy

Mặc dù đệ quy rất thanh lịch, nhưng bạn cần cẩn trọng:

Ngăn xếp (Stack Overflow): Mỗi lời gọi hàm đệ quy sẽ tiêu tốn một ít bộ nhớ trên stack (ngăn xếp). Nếu đệ quy quá sâu (gọi hàm quá nhiều lần liên tiếp mà chưa đến trường hợp cơ sở), stack có thể bị tràn (stack overflow), dẫn đến chương trình bị lỗi. Kích thước stack là có giới hạn.
Hiệu năng: Như đã thấy ở ví dụ Fibonacci, đệ quy đôi khi có thể kém hiệu quả hơn so với giải pháp lặp (iterative) do chi phí của các lời gọi hàm và khả năng tính toán trùng lặp. Trong nhiều trường hợp, giải pháp lặp sẽ nhanh hơn và sử dụng ít bộ nhớ hơn.
Khó gỡ lỗi (Debugging): Việc theo dõi luồng thực thi của các lời gọi hàm đệ quy lồng nhau có thể hơi phức tạp khi gỡ lỗi.

Bài tập ví dụ: C++ Bài 14.A3: Đến lượt ai giao bóng?

Đến lượt ai giao bóng?

FullHouse Dev đang tổ chức một giải đấu bóng bàn, trong đó Alice và Bob đang chơi một trận đấu. Bất kể ai ghi điểm, mỗi người chơi sẽ giao bóng 2 lần liên tiếp trước khi đổi lượt giao bóng. Alice là người giao bóng đầu tiên của trận đấu.

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 hai số nguyên P và Q — điểm số của Alice và Bob.

OUTPUT FORMAT

Với mỗi bộ test, xác định người chơi nào (Alice hoặc Bob) đang đến lượt giao bóng.

CONSTRAINTS

1 ≤ T ≤ 200
0 ≤ P, Q ≤ 10

Ví dụ

Input

Output

Alice
Bob
Alice
Bob

Giải thích:

Test 1: Chưa có điểm nào được ghi, đây là lượt giao bóng đầu tiên của trận đấu. Alice giao bóng lần thứ nhất.
Test 2: Đã có hai điểm được ghi. Đây là lượt giao bóng thứ ba của trận đấu. Bob giao bóng lần thứ ba.
Test 3: Đã có bốn điểm được ghi. Đây là lượt giao bóng thứ năm của trận đấu. Alice giao bóng lần thứ năm.
Test 4: Đã có mười một điểm được ghi. Đây là lượt giao bóng thứ mười hai của trận đấu. Bob giao bóng lần thứ mười hai. Chào bạn, đây là hướng dẫn giải bài tập "Đến lượt ai giao bóng?" bằng C++ mà không cung cấp code hoàn chỉnh, tập trung vào ý tưởng và cấu trúc cơ bản.

Ý tưởng chính:

Điểm mấu chốt để xác định ai là người giao bóng tiếp theo không phải là điểm số riêng lẻ của từng người (P và Q), mà là tổng số điểm đã được ghi trong trận đấu cho đến thời điểm hiện tại. Điều này là vì luật giao bóng đổi sau mỗi 2 điểm tổng cộng được ghi, bất kể ai là người ghi điểm đó.

Xác định Tổng số điểm: Tính tổng số điểm đã được ghi: TongDiem = P + Q.
Phân tích luật giao bóng:
- Alice giao bóng 2 lần đầu tiên (khi tổng điểm là 0 và 1).
- Bob giao bóng 2 lần tiếp theo (khi tổng điểm là 2 và 3).
- Alice giao bóng 2 lần tiếp theo (khi tổng điểm là 4 và 5).
- Bob giao bóng 2 lần tiếp theo (khi tổng điểm là 6 và 7).
- Và cứ tiếp tục như vậy...
Tìm quy luật dựa trên Tổng điểm: Quan sát thấy rằng lượt giao bóng đổi sau mỗi 2 điểm, tạo thành một chu kỳ lặp lại sau mỗi 4 điểm (Alice 2 lần, Bob 2 lần).
- Khi TongDiem là 0 hoặc 1, Alice giao bóng.
- Khi TongDiem là 2 hoặc 3, Bob giao bóng.
- Khi TongDiem là 4 hoặc 5, Alice giao bóng.
- Khi TongDiem là 6 hoặc 7, Bob giao bóng.
- ...
Sử dụng phép toán modulo: Phép toán modulo (%) rất hữu ích khi tìm kiếm các chu kỳ lặp lại. Chu kỳ của chúng ta là 4 điểm. Hãy xem xét TongDiem % 4:
- Nếu TongDiem % 4 là 0 hoặc 1: Alice giao bóng.
- Nếu TongDiem % 4 là 2 hoặc 3: Bob giao bóng.
Lưu ý rằng điều kiện "TongDiem % 4 là 0 hoặc 1" có thể được viết gọn là TongDiem % 4 < 2.

Cấu trúc chương trình C++:

Đọc số lượng bộ test: Đọc giá trị T.
Lặp qua các bộ test: Sử dụng vòng lặp (ví dụ: while(T--) hoặc for) để xử lý từng bộ test.
Trong mỗi bộ test:
- Đọc hai số nguyên P và Q.
- Tính tổng số điểm: int TongDiem = P + Q;
- Tính kết quả của TongDiem % 4.
- Sử dụng câu lệnh điều kiện if...else:
  - Nếu (TongDiem % 4) < 2 (hoặc kiểm tra == 0 hoặc == 1), in ra "Alice".
  - Ngược lại (tức là TongDiem % 4 là 2 hoặc 3), in ra "Bob".
- Đảm bảo in kèm ký tự xuống dòng sau mỗi kết quả (endl hoặc '\n').

Gợi ý về cú pháp C++ và std:

Sử dụng #include <iostream> để nhập/xuất dữ liệu.
Sử dụng cin để đọc input.
Sử dụng cout để in output.
Sử dụng endl hoặc '\n' cho ký tự xuống dòng.
Cấu trúc hàm main() là điểm bắt đầu chương trình.

Bạn chỉ cần áp dụng logic tính toán (P + Q) % 4 và điều kiện if/else vào cấu trúc vòng lặp xử lý các bộ test.

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

Comments

There are no comments at the moment.