Bài 14.5: Bài tập thực hành đệ quy trong C++

Chào mừng trở lại với series C++ của chúng ta! Hôm nay, chúng ta sẽ cùng nhau khám phá và thực hành một trong những kỹ thuật lập trình mạnh mẽ và đôi khi gây "lú" nhất: Đệ quy (Recursion).

Đệ quy đơn giản là một hàm tự gọi lại chính nó. Nghe có vẻ kỳ lạ phải không? Nhưng nó là một công cụ cực kỳ hiệu quả để giải quyết các vấn đề có cấu trúc tự tương tự (self-similar).

Đệ quy Hoạt Động Như Thế Nào?

Hãy tưởng tượng bạn muốn leo một cái thang. Thay vì nghĩ "bước lên từng bậc một cho đến khi tới đỉnh", một suy nghĩ đệ quy có thể là "để leo được tới đỉnh từ bậc hiện tại, tôi chỉ cần leo lên một bậc và sau đó giải quyết bài toán tương tự là leo nốt phần còn lại từ bậc mới."

Để một hàm đệ quy hoạt động đúng và không bao giờ kết thúc (gây ra lỗi Stack Overflow), nó phải có hai phần chính:

  1. Điều kiện dừng (Base Case): Đây là điều kiện mà tại đó hàm không gọi lại chính nó nữa. Nó trả về một giá trị hoặc thực hiện một hành động cụ thể để "kết thúc" chuỗi gọi đệ quy. Đây là phần cực kỳ quan trọng! Nếu thiếu nó, hàm sẽ gọi vô hạn.
  2. Bước đệ quy (Recursive Step): Đây là phần mà hàm gọi lại chính nó, nhưng thường là với một đầu vào nhỏ hơn hoặc đơn giản hơn. Mục tiêu là mỗi bước đệ quy sẽ tiến gần hơn tới điều kiện dừng.
Tại Sao Lại Dùng Đệ quy?

Đệ quy thường được dùng khi cấu trúc của bài toán phù hợp một cách tự nhiên với nó. Các ví dụ điển hình bao gồm:

  • Các bài toán liên quan đến cây (tree) hoặc đồ thị (graph).
  • Các bài toán chia để trị (Divide and Conquer).
  • Các công thức toán học định nghĩa theo đệ quy (như giai thừa, Fibonacci).
  • Duyệt cấu trúc dữ liệu lồng nhau.

Trong một số trường hợp, code viết bằng đệ quy có thể trông ngắn gọn và thanh lịch hơn đáng kể so với dùng vòng lặp. Tuy nhiên, đôi khi nó cũng khó hiểu và có thể kém hiệu quả hơn (do chi phí gọi hàm và quản lý Stack).

Hôm nay, chúng ta sẽ tập trung vào thực hành để làm quen với cách "nghĩ" theo kiểu đệ quy.

Các Bài Tập Thực Hành Đệ quy Cơ Bản

Chúng ta sẽ bắt đầu với những ví dụ kinh điển để làm nóng.

Bài Tập 1: Tính Giai Thừa (Factorial)

Bài toán: Tính giai thừa của một số nguyên không âm n, ký hiệu là n!. Định nghĩa: n! = n * (n-1) * ... * 2 * 1. Định nghĩa đệ quy:

  • 0! = 1 (Điều kiện dừng)
  • n! = n * (n-1)! với n > 0 (Bước đệ quy)

Hãy cùng xem code C++:

#include <iostream>

long long factorial(int n) {
    // Điều kiện dừng: giai thừa của 0 là 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 << num << "! = " << factorial(num) << endl; // Output: 5! = 120

    num = 0;
    cout << num << "! = " << factorial(num) << endl; // Output: 0! = 1

    return 0;
}

Giải thích: Hàm factorial(n) kiểm tra nếu n là 0 (base case), trả về 1. Nếu không, nó trả về n nhân với kết quả của factorial(n-1), tức là bài toán con đã được thu nhỏ. Quá trình này tiếp diễn cho đến khi đối số truyền vào là 0.

Bài Tập 2: Tính Số Fibonacci

Bài toán: Tính số thứ n trong dãy Fibonacci. Dãy Fibonacci bắt đầu bằng 0, 1. Số tiếp theo là tổng của hai số đứng trước nó: 0, 1, 1, 2, 3, 5, 8, 13, ... Định nghĩa đệ quy:

  • Fib(0) = 0 (Điều kiện dừng 1)
  • Fib(1) = 1 (Điều kiện dừng 2)
  • Fib(n) = Fib(n-1) + Fib(n-2) với n > 1 (Bước đệ quy)

Code C++:

#include <iostream>

int fibonacci(int n) {
    // Điều kiện dừng
    if (n <= 1) {
        return n;
    }
    // Bước đệ quy: tổng của hai số trước đó
    else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main() {
    int num = 10;
    cout << "Số Fibonacci thứ " << num << " là: " << fibonacci(num) << endl; // Output: Số Fibonacci thứ 10 là: 55

    num = 0;
    cout << "Số Fibonacci thứ " << num << " là: " << fibonacci(num) << endl; // Output: Số Fibonacci thứ 0 là: 0

    num = 1;
    cout << "Số Fibonacci thứ " << num << " là: " << fibonacci(num) << endl; // Output: Số Fibonacci thứ 1 là: 1

    return 0;
}

Giải thích: Hàm fibonacci(n) có hai base case cho n=0 và n=1. Với n > 1, nó gọi đệ quy hai lần để tính fibonacci(n-1) và fibonacci(n-2) rồi cộng chúng lại. Lưu ý: Cách triển khai Fibonacci bằng đệ quy này khá kém hiệu quả với các giá trị n lớn do tính toán lặp lại nhiều lần cùng một giá trị (ví dụ: fibonacci(3) sẽ được tính nhiều lần khi gọi fibonacci(5)).

Bài Tập 3: Tính Tổng Các Chữ Số Của Một Số Nguyên

Bài toán: Cho một số nguyên dương, tính tổng các chữ số của nó. Ví dụ: tổng chữ số của 123 là 1 + 2 + 3 = 6. Cách "nghĩ" đệ quy: Tổng chữ số của 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 n (n / 10). Định nghĩa đệ quy:

  • Tổng chữ số của 0 là 0 (Điều kiện dừng)
  • Tổng chữ số của n (với n > 0) = (n % 10) + sumDigits(n / 10) (Bước đệ quy)

Code C++:

#include <iostream>

int sumDigits(int n) {
    // Điều kiện dừng: khi số còn lại là 0
    if (n == 0) {
        return 0;
    }
    // Bước đệ quy: chữ số cuối + tổng các chữ số còn lại
    else {
        return (n % 10) + sumDigits(n / 10);
    }
}

int main() {
    int num = 456;
    cout << "Tổng các chữ số của " << num << " là: " << sumDigits(num) << endl; // Output: Tổng các chữ số của 456 là: 15

    num = 1007;
    cout << "Tổng các chữ số của " << num << " là: " << sumDigits(num) << endl; // Output: Tổng các chữ số của 1007 là: 8

    num = 0;
    cout << "Tổng các chữ số của " << num << " là: " << sumDigits(num) << endl; // Output: Tổng các chữ số của 0 là: 0

    return 0;
}

Giải thích: Hàm sumDigits(n) lấy chữ số cuối cùng (n % 10) và cộng nó với kết quả của việc gọi đệ quy chính nó với phần còn lại của số (n / 10). Quá trình này dừng khi n bằng 0.

Bài Tập 4: Tính Lũy Thừa (Power Function)

Bài toán: Tính base mũ exponent (base^exponent) với exponent là số nguyên không âm. Cách "nghĩ" đệ quy: base^exponent = base * base^(exponent-1). Định nghĩa đệ quy:

  • base^0 = 1 (Điều kiện dừng)
  • base^exponent = base * power(base, exponent - 1) với exponent > 0 (Bước đệ quy)

Code C++:

#include <iostream>

double power(double base, int exponent) {
    // Điều kiện dừng: bất kỳ số nào mũ 0 đều bằng 1
    if (exponent == 0) {
        return 1;
    }
    // Bước đệ quy: base^exponent = base * base^(exponent-1)
    else {
        return base * power(base, exponent - 1);
    }
}

int main() {
    double base = 2.0;
    int exponent = 5;
    cout << base << "^" << exponent << " = " << power(base, exponent) << endl; // Output: 2^5 = 32

    base = 3.0;
    exponent = 0;
    cout << base << "^" << exponent << " = " << power(base, exponent) << endl; // Output: 3^0 = 1

    base = 10.0;
    exponent = 3;
    cout << base << "^" << exponent << " = " << power(base, exponent) << endl; // Output: 10^3 = 1000

    return 0;
}

Giải thích: Hàm power(base, exponent) có base case khi exponent bằng 0. Nếu không, nó gọi đệ quy với exponent giảm đi 1 và nhân kết quả với base.

Bài Tập 5: Tháp Hà Nội (Tower of Hanoi)

Bài toán: Chuyển một chồng đĩa có kích thước khác nhau từ cột nguồn sang cột đích, sử dụng một cột trung gian. Đĩa lớn không bao giờ được đặt lên trên đĩa nhỏ. Đây là một bài toán kinh điển thể hiện vẻ đẹp của đệ quy. Để chuyển n đĩa từ cột A sang cột C (sử dụng cột B làm trung gian), ta thực hiện các bước sau:

  1. Chuyển n-1 đĩa nhỏ nhất từ cột A sang cột B (sử dụng C làm trung gian). (Bước đệ quy 1)
  2. Chuyển đĩa lớn nhất (đĩa thứ n) từ cột A sang cột C. (Hành động trực tiếp)
  3. Chuyển n-1 đĩa từ cột B sang cột C (sử dụng A làm trung gian). (Bước đệ quy 2)

Điều kiện dừng: Khi chỉ còn 1 đĩa (n=1), chỉ cần chuyển trực tiếp đĩa đó từ cột nguồn sang cột đích.

Code C++:

#include <iostream>
#include <string>

void towerOfHanoi(int n, char source, char auxiliary, char destination) {
    // Điều kiện dừng: chỉ còn 1 đĩa để di chuyển
    if (n == 1) {
        cout << "Chuyển đĩa 1 từ cột " << source << " sang cột " << destination << endl;
        return;
    }

    // Bước đệ quy 1: Chuyển n-1 đĩa từ source sang auxiliary, dùng destination làm trung gian
    towerOfHanoi(n - 1, source, destination, auxiliary);

    // Hành động trực tiếp: Chuyển đĩa thứ n từ source sang destination
    cout << "Chuyển đĩa " << n << " từ cột " << source << " sang cột " << destination << endl;

    // Bước đệ quy 2: Chuyển n-1 đĩa từ auxiliary sang destination, dùng source làm trung gian
    towerOfHanoi(n - 1, auxiliary, source, destination);
}

int main() {
    int num_disks = 3; // Số đĩa
    cout << "Các bước giải Tháp Hà Nội với " << num_disks << " đĩa:" << endl;
    towerOfHanoi(num_disks, 'A', 'B', 'C'); // Chuyển từ cột A sang C, dùng B trung gian

    return 0;
}

Giải thích: Hàm towerOfHanoi(n, source, auxiliary, destination) giải bài toán chuyển n đĩa. Base case là khi n=1, nó in ra bước chuyển đĩa 1. Với n > 1, nó thực hiện 3 bước:

  1. Gọi đệ quy để chuyển n-1 đĩa từ source sang auxiliary (vai trò của auxiliary và destination tạm thời đổi chỗ).
  2. In ra bước chuyển đĩa lớn nhất (n) từ source sang destination.
  3. Gọi đệ quy để chuyển n-1 đĩa từ auxiliary sang destination (vai trò của source và auxiliary lại tạm thời đổi chỗ).
Những Lưu Ý Khi Sử Dụng Đệ quy
  • Luôn có điều kiện dừng: Không có điều kiện dừng là nguyên nhân phổ biến nhất gây ra lỗi Stack Overflow (bộ nhớ gọi hàm bị tràn).
  • Bước đệ quy phải thu nhỏ bài toán: Mỗi lần gọi đệ quy, bài toán phải trở nên đơn giản hơn hoặc nhỏ hơn để cuối cùng đạt đến điều kiện dừng.
  • Xem xét hiệu suất: Đệ quy có thể tiêu tốn nhiều bộ nhớ (do lưu trữ trạng thái trên Stack) và thời gian hơn so với giải pháp lặp tương đương, đặc biệt với các bài toán như Fibonacci (đệ quy "cây" nhiều nhánh).
  • Có thể chuyển đổi sang vòng lặp: Hầu hết các bài toán giải được bằng đệ quy cũng có thể giải bằng vòng lặp (và ngược lại). Lựa chọn phương pháp nào tùy thuộc vào sự rõ ràng, hiệu quả, và bản chất của bài toán.

Comments

There are no comments at the moment.