Bài 14.1: Khái niệm và cơ chế đệ quy trong C++

Trong hành trình chinh phục C++, chúng ta đã đi qua rất nhiều khái niệm cơ bản, từ biến, kiểu dữ liệu, cấu trúc điều khiển đến hàm. Hôm nay, chúng ta sẽ chạm đến một chủ đề cực kỳ thú vị và mạnh mẽ: Đệ quy (Recursion). Đệ quy không chỉ là một kỹ thuật lập trình; nó là một cách tư duy để giải quyết vấn đề, đặc biệt hữu ích với những bài toán có cấu trúc lặp lại chính nó ở quy mô nhỏ hơn.

Hãy cùng khám phá xem đệ quy là gì và làm thế nào nó hoạt động trong C++ nhé!

Đệ quy là gì?

Nói một cách đơn giản, đệ quy là khi một hàm gọi lại chính nó trong quá trình thực thi.

Nghe có vẻ hơi khó hiểu đúng không? Hãy thử hình dung một cách khác: Bạn muốn giải quyết một bài toán lớn. Thay vì tìm cách giải quyết trực tiếp toàn bộ bài toán, bạn nhận thấy rằng bài toán lớn này có thể được chia nhỏ thành một hoặc nhiều bài toán con giống hệt bài toán ban đầu, chỉ khác về quy mô. Nếu bạn biết cách giải quyết bài toán con nhỏ hơn, bạn có thể sử dụng giải pháp đó để giúp giải quyết bài toán lớn hơn. Đệ quy chính là hiện thực hóa ý tưởng này trong code.

Một hình ảnh trực quan khác là hiệu ứng khi bạn đặt hai chiếc gương đối diện nhau; bạn sẽ thấy hình ảnh của chính mình lặp đi lặp lại vô tận. Đệ quy trong lập trình cũng có ý tưởng tương tự, nhưng bắt buộc phải có một "điểm dừng" để tránh sự vô tận và kết thúc quá trình thực thi.

Hai Trụ Cột của Đệ quy

Để một hàm đệ quy hoạt động đúng đắn, nó cần có hai thành phần thiết yếu:

  1. Cơ sở (Base Case):

    • Đây là điểm dừng của quá trình đệ quy.
    • Nó là một điều kiện hoặc một tập hợp các điều kiện mà khi được đáp ứng, hàm sẽ trả về một giá trị hoặc thực hiện một hành động mà không gọi lại chính nó.
    • Điều kiện cơ sở phải được đáp ứng tại một thời điểm nào đó trong quá trình đệ quy. Nếu không có cơ sở, hoặc cơ sở không bao giờ đạt tới, đệ quy sẽ chạy mãi mãi dẫn đến lỗi Stack Overflow.

  2. Bước đệ quy (Recursive Step):

    • Đây là phần mà hàm gọi lại chính nó.
    • Trong bước này, hàm thường giải quyết một phần nhỏ của bài toán ban đầu và sau đó gọi lại chính nó để giải quyết phần còn lại.
    • Quan trọng là mỗi lần gọi đệ quy trong bước này phải làm cho bài toán con nhỏ hơn hoặc đơn giản hơn, tiến gần hơn đến điều kiện cơ sở.

Nếu thiếu một trong hai trụ cột này, hàm đệ quy sẽ không bao giờ dừng lại (thiếu cơ sở) hoặc không bao giờ thực sự sử dụng đệ quy (thiếu bước đệ quy).

Cơ chế hoạt động (Bên dưới lớp vỏ)

Khi một hàm được gọi trong C++ (dù là gọi thông thường hay gọi đệ quy), hệ thống sẽ tạo một frame hoặc record kích hoạt cho lần gọi đó và đẩy nó vào một vùng nhớ đặc biệt gọi là ngăn xếp cuộc gọi (call stack). Frame này chứa thông tin cần thiết cho lần thực thi cụ thể đó, bao gồm:

  • Giá trị của các tham số truyền vào.
  • Các biến cục bộ của hàm.
  • Địa chỉ mà chương trình sẽ quay về sau khi hàm kết thúc.

Khi một hàm đệ quy gọi lại chính nó, một frame mới lại được tạo cho lần gọi mới đó và tiếp tục được đẩy vào đỉnh của call stack. Quá trình này tiếp diễn.

Khi điều kiện cơ sở được đáp ứng, lần gọi đệ quy hiện tại sẽ trả về kết quả. Frame tương ứng của lần gọi này sẽ được loại bỏ khỏi call stack. Sau đó, chương trình quay trở lại frame của lần gọi đệ quy trước đó (ngay bên dưới trong stack), sử dụng kết quả vừa trả về để tiếp tục tính toán hoặc xử lý, cho đến khi frame đó cũng hoàn thành và được loại bỏ. Quá trình này lặp lại cho đến khi frame đầu tiên (frame của lần gọi đệ quy ban đầu từ hàm main hoặc hàm khác) hoàn thành.

Cơ chế call stack là yếu tố then chốt giúp theo dõi các lần gọi đệ quy lồng nhau và quay trở lại đúng điểm sau khi mỗi lần gọi hoàn thành.

Ví dụ Minh họa

Để hiểu rõ hơn, chúng ta hãy xem xét một vài ví dụ cổ điển và phổ biến về đệ quy.

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

Giai thừa của một số nguyên không âm 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. Ví dụ: 5! = 5 4 3 2 1 = 120.

Chúng ta có thể định nghĩa giai thừa một cách đệ quy như sau:

  • n! = n * (n-1)! với n > 1 (Đây là bước đệ quy)
  • 1! = 1 (Đây là cơ sở 1)
  • 0! = 1 (Đây là cơ sở 2)

Trong C++, chúng ta có thể viết hàm tính giai thừa bằng đệ quy như sau:

#include <iostream>

// Hàm tính giai thừa sử dụng đệ quy
int factorial(int n) {
    // Kiểm tra điều kiện cơ sở (base case)
    if (n <= 1) {
        return 1; // 0! = 1 và 1! = 1
    }
    // Bước đệ quy (recursive step)
    // n! = n * (n-1)!
    else {
        return n * factorial(n - 1);
    }
}

int main() {
    int num = 5;
    cout << "Giai thừa của " << num << " là: " << factorial(num) << endl; // Output: Giai thừa của 5 là: 120

    num = 0;
    cout << "Giai thừa của " << num << " là: " << factorial(num) << endl; // Output: Giai thừa của 0 là: 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 9: Kiểm tra điều kiện cơ sở: nếu n nhỏ hơn hoặc bằng 1, hàm trả về 1 và dừng lại (không gọi đệ quy).
  • Dòng 14: Nếu n lớn hơn 1, đây là bước đệ quy. Hàm trả về kết quả bằng n nhân với kết quả của hàm factorial gọi với đối số n - 1. Chú ý rằng n - 1 luôn nhỏ hơn n, đảm bảo rằng lời gọi đệ quy tiếp theo tiến gần hơn đến điều kiện cơ sở (n <= 1).
  • Trong main, chúng ta gọi factorial với các giá trị khác nhau để kiểm tra.

Khi bạn gọi factorial(5), quá trình sẽ diễn ra như sau trên call stack:

  1. factorial(5) được gọi -> Push factorial(5) frame. 5 > 1. Tính 5 * factorial(4).
  2. factorial(4) được gọi -> Push factorial(4) frame. 4 > 1. Tính 4 * factorial(3).
  3. factorial(3) được gọi -> Push factorial(3) frame. 3 > 1. Tính 3 * factorial(2).
  4. factorial(2) được gọi -> Push factorial(2) frame. 2 > 1. Tính 2 * factorial(1).
  5. factorial(1) được gọi -> Push factorial(1) frame. 1 <= 1. Đạt cơ sở. Trả về 1. Pop factorial(1) frame.
  6. Quay lại factorial(2). Nhận kết quả factorial(1) là 1. Tính 2 * 1 = 2. Trả về 2. Pop factorial(2) frame.
  7. Quay lại factorial(3). Nhận kết quả factorial(2) là 2. Tính 3 * 2 = 6. Trả về 6. Pop factorial(3) frame.
  8. Quay lại factorial(4). Nhận kết quả factorial(3) là 6. Tính 4 * 6 = 24. Trả về 24. Pop factorial(4) frame.
  9. Quay lại factorial(5). Nhận kết quả factorial(4) là 24. Tính 5 * 24 = 120. Trả về 120. Pop factorial(5) frame.
  10. Chương trình kết thúc.
Ví dụ 2: Dãy Fibonacci

Dãy 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ố liền trước nó. Dãy bắt đầu như sau: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Công thức đệ quy của dãy Fibonacci:

  • F(n) = F(n-1) + F(n-2) với n > 1 (Đây là bước đệ quy)
  • F(0) = 0 (Đây là cơ sở 1)
  • F(1) = 1 (Đây là cơ sở 2)

Chúng ta có thể viết hàm tính số Fibonacci thứ n bằng đệ quy như sau:

#include <iostream>

// Hàm tính số Fibonacci thứ n sử dụng đệ quy
int fibonacci(int n) {
    // Kiểm tra các điều kiện cơ sở (base cases)
    if (n <= 1) {
        return n; // Trả về 0 nếu n=0, 1 nếu n=1
    }
    // Bước đệ quy (recursive step)
    // F(n) = F(n-1) + F(n-2)
    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 code:

  • Hàm fibonacci(int n) nhận vào chỉ số n của số Fibonacci cần tính.
  • Dòng 9: Kiểm tra điều kiện cơ sở. Nếu n nhỏ hơn hoặc bằng 1, hàm trả về chính n. Điều này xử lý cả F(0) = 0 và F(1) = 1.
  • Dòng 14: Nếu n lớn hơn 1, đây là bước đệ quy. Hàm trả về tổng của hai lần gọi đệ quy: fibonacci(n - 1) và fibonacci(n - 2). Cả n - 1 và n - 2 đều nhỏ hơn n, đảm bảo tiến gần đến cơ sở.

Lưu ý về hiệu suất: Cách tính Fibonacci đệ quy trực tiếp này rất thanh lịch vì nó ánh xạ trực tiếp định nghĩa toán học, nhưng nó lại không hiệu quả đối với các giá trị n lớn. Lý do là nó tính toán lại cùng một giá trị Fibonacci 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). Bạn có thể thấy F(3) được tính hai lần). Điều này dẫn đến số lượng cuộc gọi hàm tăng theo cấp số nhân. Có những cách tối ưu hóa đệ quy (như đệ quy có nhớ - memoization) hoặc sử dụng phương pháp lặp (iteration) để tính Fibonacci hiệu quả hơn. Tuy nhiên, xét về khía cạnh minh họa khái niệm đệ quy đơn thuần, ví dụ này là rất tốt.

Ví dụ 3: Tháp Hà Nội (Tower of Hanoi)

Tháp Hà Nội là một bài toán cổ điển thường được sử dụng để minh họa đệ quy. Bài toán như sau: Bạn có ba chiếc cọc (gọi là cọc nguồn Source, cọc trung gian Auxiliary, và cọc đích Destination) và n đĩa có kích thước khác nhau xếp chồng lên nhau trên cọc nguồn, từ đĩa lớn nhất ở dưới cùng đến đĩa nhỏ nhất ở trên cùng. Mục tiêu là chuyển toàn bộ chồng đĩa từ cọc nguồn sang cọc đích, tuân theo các quy tắc sau:

  1. Chỉ được chuyển một đĩa mỗi lần.
  2. Chỉ được chuyển đĩa trên cùng của một cọc.
  3. Không bao giờ được đặt đĩa lớn hơn lên trên đĩa nhỏ hơn.

Làm sao để giải quyết bài toán này? Hãy nghĩ một cách đệ quy:

  • Cơ sở (Base Case): Nếu chỉ có 1 đĩa (n=1), bạn chỉ cần chuyển đĩa đó trực tiếp từ cọc nguồn sang cọc đích. Đây là bước dừng.
  • Bước đệ quy (Recursive Step): Để chuyển n đĩa từ Source sang Destination sử dụng Auxiliary, bạn thực hiện 3 bước con:
    1. Chuyển n-1 đĩa từ Source sang Auxiliary, sử dụng Destination làm cọc trung gian. (Đây là một bài toán con đệ quy nhỏ hơn).
    2. Chuyển đĩa thứ n (đĩa lớn nhất) từ Source sang Destination. (Đây là một bước trực tiếp).
    3. Chuyển n-1 đĩa từ Auxiliary sang Destination, sử dụng Source làm cọc trung gian. (Đây lại là một bài toán con đệ quy nhỏ hơn).

Bạn thấy không? Để giải bài toán với n đĩa, chúng ta quy về giải bài toán với n-1 đĩa.

Code C++ cho bài toán Tháp Hà Nội (chỉ in ra các bước di chuyển):

#include <iostream>
#include <string>

// Hàm giải bài toán Tháp Hà Nội
// n: số đĩa cần chuyển
// source: tên cọc nguồn
// auxiliary: tên cọc trung gian
// destination: tên cọc đích
void towerOfHanoi(int n, char source, char auxiliary, char destination) {
    // Kiểm tra điều kiện cơ sở (base case)
    if (n == 1) {
        cout << "Chuyển đĩa 1 từ " << source << " sang " << destination << endl;
        return; // Dừng đệ quy
    }

    // Bước đệ quy (recursive steps)

    // 1. Chuyển n-1 đĩa từ cột nguồn sang cột trung gian, dùng cột đích làm trung gian tạm thời
    towerOfHanoi(n - 1, source, destination, auxiliary);

    // 2. Chuyển đĩa thứ n từ cột nguồn sang cột đích
    cout << "Chuyển đĩa " << n << " từ " << source << " sang " << destination << endl;

    // 3. Chuyển n-1 đĩa từ cột trung gian sang cột đích, dùng cột nguồn làm trung gian tạm thời
    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;
    // Gọi hàm đệ quy để giải bài toán: Chuyển 3 đĩa từ 'A' sang 'C', dùng 'B' làm trung gian
    towerOfHanoi(num_disks, 'A', 'B', 'C');
    return 0;
}

Giải thích code:

  • Hàm towerOfHanoi nhận số đĩa n và tên của ba cọc (dưới dạng ký tự char).
  • Dòng 11: Điều kiện cơ sở: nếu n bằng 1, chúng ta in ra bước di chuyển đĩa 1 và hàm kết thúc.
  • Dòng 18: Bước đệ quy 1: Gọi lại towerOfHanoi để chuyển n-1 đĩa. Các tham số được truyền khéo léo: nguồn là source, đích là auxiliary, và cọc trung gian lúc này là destination (vì mục tiêu tạm thời là chuyển n-1 đĩa đến cọc auxiliary).
  • Dòng 21: Bước trực tiếp: Sau khi n-1 đĩa đã ở cọc trung gian, đĩa lớn nhất (đĩa n) ở cọc nguồn đã trống, ta chuyển nó sang cọc đích.
  • Dòng 24: Bước đệ quy 3: Gọi lại towerOfHanoi để chuyển n-1 đĩa từ cọc auxiliary (nơi chúng đang tạm trú) sang cọc đích. Lúc này, cọc auxiliary trở thành nguồn (auxiliary), cọc đích vẫn là đích (destination), và cọc source ban đầu trở thành cọc trung gian tạm thời (source).
  • Trong main, chúng ta gọi hàm với 3 đĩa và tên các cọc 'A', 'B', 'C'.

Bài toán Tháp Hà Nội minh họa rất rõ sức mạnh của đệ quy trong việc giải các vấn đề mà cấu trúc của chúng tự lặp lại. Code trông khá ngắn gọn nhưng giải quyết được một bài toán phức tạp!

Những lưu ý và hạn chế

Mặc dù đệ quy rất thanh lịch và là công cụ mạnh mẽ, nó không phải là viên đạn bạc cho mọi vấn đề. Có một vài điều cần lưu ý:

  1. Stack Overflow: Như đã đề cập, nếu hàm đệ quy chạy quá sâu (gọi lại chính nó quá nhiều lần) mà chưa đạt đến điều kiện cơ sở, call stack sẽ đầy và gây ra lỗi Stack Overflow. Điều này xảy ra khi không có cơ sở hoặc khi bước đệ quy không thu nhỏ bài toán đúng cách.
  2. Hiệu suất: Mỗi lần gọi hàm đệ quy đều tốn một chút chi phí (overhead) để tạo và quản lý frame trên call stack. Đối với một số bài toán, giải pháp lặp (sử dụng vòng lặp for, while) có thể hiệu quả hơn về mặt thời gian chạy và bộ nhớ so với đệ quy đơn giản. Ví dụ Fibonacci là một minh họa điển hình.
  3. Độ phức tạp: Đôi khi, việc theo dõi luồng thực thi của một hàm đệ quy có thể khó khăn hơn so với hàm lặp, đặc biệt với đệ quy lồng nhau hoặc có nhiều nhánh rẽ.
Khi nào nên sử dụng đệ quy?

Đệ quy thường là lựa chọn tốt khi:

  • Cấu trúc của bài toán hoặc dữ liệu (như cây, đồ thị) có tính chất đệ quy tự nhiên. Ví dụ: duyệt cây, tìm kiếm trong cây nhị phân.
  • Công thức định nghĩa bài toán mang tính đệ quy rõ ràng (như giai thừa, Fibonacci, Tháp Hà Nội).
  • Giải pháp đệ quy làm cho code trở nên rõ ràng và dễ đọc hơn so với giải pháp lặp tương đương.

Hầu hết các bài toán giải được bằng đệ quy cũng có thể giải được bằng vòng lặp (iteration), và ngược lại. Việc lựa chọn phương pháp nào tùy thuộc vào sự cân bằng giữa độ rõ ràng của code, hiệu suất và yêu cầu cụ thể của bài toán.

Tóm lại

Đệ quy là một kỹ thuật lập trình mạnh mẽ cho phép một hàm tự gọi chính nó. Nó bao gồm hai phần cốt lõi: cơ sở (base case) để dừng lại và bước đệ quy (recursive step) để thu nhỏ bài toán. Đệ quy hoạt động dựa trên cơ chế ngăn xếp cuộc gọi (call stack) của hệ thống. Mặc dù đệ quy có thể dẫn đến code thanh lịch và trực tiếp ánh xạ nhiều định nghĩa toán học hoặc cấu trúc dữ liệu, cần phải cẩn trọng với nguy cơ Stack Overflow và đôi khi là vấn đề về hiệu suất so với giải pháp lặp. Hiểu và sử dụng thành thạo đệ quy là một bước tiến quan trọng trong hành trình trở thành lập trình viên chuyên nghiệp.

Hy vọng bài viết này đã giúp bạn hiểu rõ hơn về khái niệm và cơ chế của đệ quy trong C++.

Comments

There are no comments at the moment.