Bài 15.3: Bài tập thực hành đệ quy cơ bản trong C++

Chào mừng trở lại với chuỗi bài blog về C++! Sau khi chúng ta đã cùng nhau khám phá lý thuyết đệ quy ở bài trước, giờ là lúc xắn tay áo lên và bắt đầu thực hành. Lý thuyết chỉ là nền móng, chính việc áp dụng vào các bài toán cụ thể mới giúp chúng ta thực sự hiểu và làm chủ kỹ thuật lập trình mạnh mẽ này.

Đệ quy có thể ban đầu hơi "xoắn não", nhưng đừng lo lắng! Qua những bài tập cơ bản dưới đây, bạn sẽ dần làm quen với cách tư duy theo hướng đệ quy, một kỹ năng cực kỳ hữu ích trong lập trình giải thuật và cấu trúc dữ liệu.

Nhắc lại nhanh: Đệ quy là gì?

Đơn giản mà nói, đệ quy là khi một hàm tự gọi lại chính nó. Để đệ quy hoạt động đúng và không rơi vào vòng lặp vô hạn, nó cần có hai thành phần cốt lõi:

Điều kiện dừng (Base Case): Đây là điều kiện để hàm ngừng gọi đệ quy. Khi điều kiện này đúng, hàm sẽ trả về một giá trị hoặc thực hiện một hành động cuối cùng mà không gọi lại chính nó nữa. Điều kiện dừng là cốt lõi để tránh "lặp vô hạn" và sập chương trình.
Bước đệ quy (Recursive Step): Đây là nơi hàm gọi lại chính nó, thường với một đối số đã thay đổi sao cho tiến dần về điều kiện dừng.

Bây giờ, chúng ta hãy cùng nhau đi qua một vài bài tập thực hành cơ bản nhất để làm quen với cách áp dụng hai thành phần này nhé!

Bài tập 1: Tính giai thừa (Factorial)

Đề bài: Viết hàm đệ quy để tính giai thừa của một số nguyên không âm n. Giai thừa của n (ký hiệu là n!) được định nghĩa là tích của tất cả các số nguyên dương từ 1 đến n. Quy ước 0! = 1.

Ví dụ: 5! = 5 4 3 2 1 = 120.

Phân tích đệ quy:

Điều kiện dừng (Base Case): Khi nào chúng ta biết chắc chắn kết quả mà không cần gọi đệ quy nữa? Đó là khi n = 0 hoặc n = 1. Lúc đó, giai thừa là 1.
Bước đệ quy (Recursive Step): Với n > 1, chúng ta có thể biểu diễn n! thông qua giai thừa của một số nhỏ hơn. Cụ thể, n! = n * (n-1)!. Đây chính là bước đệ quy! Chúng ta gọi lại hàm tính giai thừa nhưng với đối số n-1.

Code C++:

#include <iostream>

// Hàm tính giai thừa sử dụng đệ quy
long long factorial(int n) {
    // Điều kiện dừng: khi n là 0 hoặc 1
    if (n == 0 || n == 1) {
        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 << " (" << num << "!) la: " << factorial(num) << endl; // Output: Giai thua cua 5 (5!) la: 120

    int num2 = 0;
    cout << "Giai thua cua " << num2 << " (" << num2 << "!) la: " << factorial(num2) << endl; // Output: Giai thua cua 0 (0!) la: 1

    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 || n == 1) kiểm tra điều kiện dừng. Nếu n là 0 hoặc 1, hàm trả về 1 ngay lập tức và quá trình đệ quy cho nhánh này kết thúc.
Khối else chứa bước đệ quy. Tại đây, hàm trả về kết quả của phép nhân n với kết quả của chính hàm factorial được gọi với đối số n - 1. Điều này lặp lại cho đến khi đối số đạt đến 1 hoặc 0.
Hàm main chỉ đơn giản là ví dụ minh họa cách gọi hàm factorial và in kết quả ra màn hình sử dụng cout. Chúng ta dùng kiểu long long cho kết quả để tránh tràn số với các giá trị giai thừa lớn.

Bài tập 2: Tính số Fibonacci thứ n

Đề bài: Viết hàm đệ quy để tính số Fibonacci thứ n. Dãy Fibonacci bắt đầu bằng 0 và 1, các số tiếp theo là tổng của hai số đứng trước nó: 0, 1, 1, 2, 3, 5, 8, 13, ...

Ví dụ: Số Fibonacci thứ 6 là 8 (vì 0, 1, 1, 2, 3, 5, 8).

Phân tích đệ quy:

Điều kiện dừng (Base Cases): Hai số đầu tiên của dãy đã được định nghĩa sẵn:
- Fibonacci thứ 0 là 0.
- Fibonacci thứ 1 là 1.
Bước đệ quy (Recursive Step): Với n > 1, số Fibonacci thứ n được tính bằng tổng của số Fibonacci thứ n-1 và số Fibonacci thứ n-2. Đây là công thức đệ quy trực tiếp!

Code C++:

#include <iostream>

// Hàm tính số Fibonacci thứ n sử dụng đệ quy
int fibonacci(int n) {
    // Điều kiện dừng: cho F(0) và F(1)
    if (n <= 1) {
        return n; // Trả về 0 nếu n=0, trả về 1 nếu n=1
    }
    // 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: So Fibonacci thu 6 la: 8

    int num2 = 0;
    cout << "So Fibonacci thu " << num2 << " la: " << fibonacci(num2) << endl; // Output: So Fibonacci thu 0 la: 0

    int num3 = 1;
    cout << "So Fibonacci thu " << num3 << " la: " << fibonacci(num3) << endl; // Output: So Fibonacci thu 1 la: 1

    return 0;
}

Giải thích Code:

Hàm fibonacci(int n) nhận vào chỉ số n của số Fibonacci cần tìm.
Dòng if (n <= 1) kiểm tra điều kiện dừng. Nếu n là 0 hoặc 1, hàm trả về chính giá trị của n. Đây là cách gộp chung hai điều kiện dừng F(0)=0 và F(1)=1.
Khối else chứa bước đệ quy. Hàm trả về tổng của hai cuộc gọi đệ quy: fibonacci(n - 1) và fibonacci(n - 2). Lưu ý là hàm gọi chính nó hai lần trong bước này.
Hàm main minh họa cách sử dụng.

Lưu ý: Cách tính Fibonacci bằng đệ quy "ngây thơ" này rất dễ hiểu nhưng lại không hiệu quả lắm với các giá trị n lớn do có nhiều phép tính trùng lặp. Tuy nhiên, nó là một ví dụ tuyệt vời để hiểu cách đệ quy hoạt động với nhiều nhánh gọi.

Bài tập 3: Tính tổng các số từ 1 đến n

Đề bài: Viết hàm đệ quy để tính tổng của tất cả các số nguyên dương từ 1 đến n.

Ví dụ: Tổng từ 1 đến 5 là 1 + 2 + 3 + 4 + 5 = 15.

Phân tích đệ quy:

Điều kiện dừng (Base Case): Tổng từ 1 đến 0 là 0. Đây là điểm dừng hợp lý.
Bước đệ quy (Recursive Step): Tổng từ 1 đến n có thể được tính bằng n cộng với tổng từ 1 đến n-1.

Code C++:

#include <iostream>

// Hàm tính tổng từ 1 đến n sử dụng đệ quy
int sum_up_to(int n) {
    // Điều kiện dừng: khi n <= 0, tổng là 0
    if (n <= 0) {
        return 0;
    }
    // Bước đệ quy: Tong(n) = n + Tong(n-1)
    else {
        return n + sum_up_to(n - 1);
    }
}

int main() {
    int num = 10;
    cout << "Tong tu 1 den " << num << " la: " << sum_up_to(num) << endl; // Output: Tong tu 1 den 10 la: 55

    int num2 = 0;
     cout << "Tong tu 1 den " << num2 << " la: " << sum_up_to(num2) << endl; // Output: Tong tu 1 den 0 la: 0

    return 0;
}

Giải thích Code:

Hàm sum_up_to(int n) nhận vào giới hạn trên n.
Dòng if (n <= 0) kiểm tra điều kiện dừng. Nếu n không còn là số dương (hoặc là 0), hàm trả về 0.
Khối else là bước đệ quy. Hàm trả về n cộng với kết quả của cuộc gọi đệ quy sum_up_to(n - 1). Quá trình này lặp lại cho đến khi đối số truyền vào nhỏ hơn hoặc bằng 0.

Bài tập 4: In dãy số giảm dần rồi tăng dần

Đề bài: Viết hàm đệ quy nhận vào một số nguyên dương n. Hàm này sẽ in ra các số từ n về 1 (theo thứ tự giảm dần), sau đó in lại các số từ 2 đến n (theo thứ tự tăng dần, không in lại số 1).

Ví dụ: Với n = 3, đầu ra sẽ là: 3 2 1 2 3

Phân tích đệ quy: Bài này thú vị ở chỗ hành động in (cout) xảy ra ở hai vị trí khác nhau: trước và sau cuộc gọi đệ quy.

Điều kiện dừng (Base Case): Khi n nhỏ hơn hoặc bằng 0, không cần in gì nữa và dừng lại.
Bước đệ quy (Recursive Step):
1. In ra số n hiện tại (để có dãy giảm dần).
2. Gọi đệ quy với n-1 (để xử lý phần còn lại của dãy).
3. Sau khi cuộc gọi đệ quy n-1 hoàn thành (tức là đã in xong từ n-1 về 1), in lại số n hiện tại (để có dãy tăng dần). Cần chú ý điều kiện để không in số 1 hai lần.

Code C++:

#include <iostream>

// Hàm in dãy giảm rồi tăng sử dụng đệ quy
void print_decreasing_then_increasing(int n) {
    // Điều kiện dừng
    if (n <= 0) {
        return;
    }

    // Bước 1: In số hiện tại (phần giảm dần)
    cout << n << " ";

    // Bước 2: Gọi đệ quy với n-1
    print_decreasing_then_increasing(n - 1);

    // Bước 3: In lại số hiện tại (phần tăng dần), chỉ khi n > 1
    // Điều kiện n > 1 là để tránh in số 1 lần thứ hai sau khi print_decreasing_then_increasing(1) kết thúc
    if (n > 1) {
        cout << n << " ";
    }
}

int main() {
    int num = 5;
    cout << "Ket qua voi n = " << num << ": ";
    print_decreasing_then_increasing(num); // Output: Ket qua voi n = 5: 5 4 3 2 1 2 3 4 5
    cout << endl; // In xuống dòng cuối cùng

    int num2 = 1;
    cout << "Ket qua voi n = " << num2 << ": ";
    print_decreasing_then_increasing(num2); // Output: Ket qua voi n = 1: 1
    cout << endl;

    return 0;
}

Giải thích Code:

Hàm print_decreasing_then_increasing(int n) nhận vào số nguyên dương n.
Dòng if (n <= 0) là điều kiện dừng. Khi n không còn dương, hàm dừng lại.
cout << n << " "; là hành động trước cuộc gọi đệ quy. Điều này đảm bảo các số được in ra theo thứ tự giảm dần khi hàm được gọi xuống các cấp thấp hơn.
print_decreasing_then_increasing(n - 1); là bước đệ quy chính. Hàm tự gọi nó để xử lý dãy số nhỏ hơn.
if (n > 1) { cout << n << " "; } là hành động sau cuộc gọi đệ quy hoàn thành và hàm đang "đi ngược" trở lên. Nó in ra giá trị n của lần gọi hàm hiện tại. Điều kiện n > 1 được thêm vào để số 1 chỉ được in ra một lần (khi lần gọi với n=1 thực hiện cout << n << " "; đầu tiên).

Hãy thử theo dấu cuộc gọi print_decreasing_then_increasing(3) để hiểu rõ hơn:

print_decreasing_then_increasing(3):
- n=3. n <= 0 sai.
- In 3.
- Gọi print_decreasing_then_increasing(2).
- ...Chờ cuộc gọi print_decreasing_then_increasing(2) kết thúc...
- n=3. n > 1 đúng. In 3.
- Hàm print_decreasing_then_increasing(3) kết thúc.
print_decreasing_then_increasing(2) (được gọi từ bên trong print_decreasing_then_increasing(3)):
- n=2. n <= 0 sai.
- In 2.
- Gọi print_decreasing_then_increasing(1).
- ...Chờ cuộc gọi print_decreasing_then_increasing(1) kết thúc...
- n=2. n > 1 đúng. In 2.
- Hàm print_decreasing_then_increasing(2) kết thúc và trả về cho print_decreasing_then_increasing(3).
print_decreasing_then_increasing(1) (được gọi từ bên trong print_decreasing_then_increasing(2)):
- n=1. n <= 0 sai.
- In 1.
- Gọi print_decreasing_then_increasing(0).
- ...Chờ cuộc gọi print_decreasing_then_increasing(0) kết thúc...
- n=1. n > 1 sai. Không in gì.
- Hàm print_decreasing_then_increasing(1) kết thúc và trả về cho print_decreasing_then_increasing(2).
print_decreasing_then_increasing(0) (được gọi từ bên trong print_decreasing_then_increasing(1)):
- n=0. n <= 0 đúng.
- Return ngay lập tức.

Kết quả in ra theo thứ tự: 3 (từ P(3)), 2 (từ P(2)), 1 (từ P(1)), rồi khi trở về: 2 (từ P(2) sau đệ quy), 3 (từ P(3) sau đệ quy). Tổng cộng: 3 2 1 2 3.

Một số lưu ý khi giải bài tập đệ quy

Luôn xác định rõ Điều kiện dừng (Base Case): Đây là bước quan trọng nhất. Hãy tự hỏi: Khi nào thì bài toán đủ đơn giản để giải ngay lập tức mà không cần gọi đệ quy nữa?
Xác định Bước đệ quy (Recursive Step): Giả sử bạn đã có lời giải cho bài toán nhỏ hơn (tiến dần về điều kiện dừng), làm thế nào để từ lời giải đó xây dựng nên lời giải cho bài toán lớn hơn?
Đảm bảo tiến gần đến Điều kiện dừng: Mỗi lần gọi đệ quy, đối số (hoặc trạng thái của bài toán) phải thay đổi theo hướng tiến đến điều kiện dừng. Nếu không, bạn sẽ bị lặp vô hạn (Stack Overflow).
Hiểu luồng thực thi: Đệ quy hoạt động dựa trên Stack của hệ thống. Khi hàm gọi đệ quy, trạng thái hiện tại được lưu vào stack và hàm con được thực thi. Khi hàm con kết thúc, trạng thái trước đó được khôi phục từ stack. Với các bài như in tăng dần/giảm dần, việc theo dấu Stack giúp hiểu rõ hơn hành động nào xảy ra trước và sau cuộc gọi đệ quy.

Comments

There are no comments at the moment.