Đệ quy trong C++ (Recursion)

Giới thiệu

Bạn đã từng nghe về đệ quy trong lập trình C++ chưa? Trong bài viết trước, chúng ta đã tìm hiểu về con trỏ hàm trong C++. Hôm nay, mình sẽ giới thiệu đến các bạn khái niệm đệ quy trong C++.

Nội dung

Để hiểu rõ bài viết này, bạn nên có kiến thức cơ bản về hàm và giá trị trả về trong C++.

Trong bài viết này, mình sẽ giới thiệu các vấn đề sau:

• Đệ quy là gì?
• Điều kiện dừng (điều kiện cơ sở)
• Một số bài toán đệ quy kinh điển
• Đệ quy so với vòng lặp

Đệ quy là gì?

Một hàm được gọi là đệ quy nếu bên trong thân hàm có một lời gọi đến chính nó. Hàm đệ quy luôn có điều kiện dừng được gọi là "điểm neo". Khi đạt tới điểm neo, hàm sẽ không gọi chính nó nữa.

Khi được gọi, hàm đệ quy thường được truyền một tham số, thường là kích thước của bài toán ban đầu. Sau mỗi lần gọi đệ quy, tham số sẽ nhỏ dần, nhằm phản ánh bài toán đã nhỏ hơn và đơn giản hơn. Khi tham số đạt tới một giá trị cực tiểu (tại điểm neo), hàm sẽ chấm dứt.

Ví dụ:

#include 
using namespace std;

void countDown(int count) {
    cout  "push "  count  '\n';
    countDown(count - 1); // countDown() tự gọi lại chính nó
}

int main() {
    countDown(3);
    return 0;
}

// Output:
// push 3
// push 2
// push 1

Trong chương trình trên, khi countDown(3) được gọi, thì "push 3" được in ra và countDown(2) được gọi. Sau đó countDown(2) in "push 2" và gọi countDown(1). Sau đó countDown(1) in "push 1" và gọi countDown(0). Việc này được lặp lại vô hạn, đây là một hàm đệ quy lặp vô hạn.

Điều kiện dừng (điều kiện cơ sở)

Hàm đệ quy phải có một điều kiện kết thúc đệ quy, nếu không chương trình sẽ lặp vô hạn (đến khi tràn bộ nhớ ngăn xếp). Điều kiện dừng của hàm đệ quy được gọi là điều kiện cơ sở.

Ví dụ:

#include 
using namespace std;

void countDown(int count) {
    cout  "push "  count  '\n';
    if (count > 1) // điều kiện dừng
        countDown(count - 1);
    cout  "pop "  count  '\n';
}

int main() {
    countDown(3);
    return 0;
}

// Output:
// push 3
// push 2
// push 1
// pop 1
// pop 2

Trong chương trình trên, do có điều kiện kết thúc (count > 1), nên trong hàm countDown(1) không gọi countDown(0), vì vậy "pop 1" được in ra và kết thúc hàm countDown(1). Lúc này, hàm countDown(1) bật ra khỏi ngăn xếp, hàm countDown(2) tiếp tục thực thi tại vị trí sau lời gọi hàm countDown(1), do đó "pop 2" được in ra. Tuần tự đến khi thoát ra toàn bộ các lời gọi hàm đệ quy.

Một số bài toán đệ quy kinh điển

Bài toán tính giai thừa

Cho n là một số tự nhiên (n >= 0). Hãy tính giai thừa của n (n!). Biết rằng 0! = 1 và n! = (n-1)! * n.

Phân tích:

• Để tính n!, ta cần phải tính (n-1)!
• Để tính (n-1)!, ta phải tính (n-2)!
• Và tiếp tục như vậy cho tới khi gặp trường hợp 0!. Khi đó ta lập tức có kết quả là 1, không cần phải tính thông qua một kết quả trung gian khác.

long GiaiThua(int n) {
    if (n == 0) {
        return 1; // điều kiện dừng
    }
    return n * GiaiThua(n - 1); // gọi đệ quy
}

Dãy Fibonaci

Dãy Fibonaci là dãy vô hạn các số tự nhiên. Số Fibonaci thứ n, ký hiệu F(n), được định nghĩa như sau:

• F(n) = 0, nếu n = 0
• F(n) = 1, nếu n = 1
• F(n) = F(n-1) + F(n-2), nếu n > 1

#include 
using namespace std;

int fibonacci(int number) {
    if (number == 0) return 0; // điều kiện dừng
    if (number == 1) return 1; // điều kiện dừng
    return fibonacci(number - 1) + fibonacci(number - 2);
}

int main() {
    // in dãy 15 số fibonacci
    for (int count = 0; count  15; ++count)
        cout  fibonacci(count)  " ";
    return 0;
}

// Output: 
// 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

Đệ quy so với vòng lặp

Một câu hỏi thường gặp là: "Tại sao lại sử dụng hàm đệ quy trong khi bạn có thể thực hiện với vòng lặp?".

Thông thường, các bài toán đệ quy có thể giải quyết bằng vòng lặp. Tuy nhiên, hàm đệ quy giúp code dễ đọc và đơn giản hơn.

Ví dụ: In dãy Fibonacci

#include 
using namespace std;

int main() {
    int n1 = 0, n2 = 1;
    for (int i = 1; i = 15; ++i) {
        cout  n1  " ";
        int nextTerm = n1 + n2;
        n1 = n2;
        n2 = nextTerm;
    }
    return 0;
}

// Output:
// 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

Sử dụng vòng lặp thường có hiệu suất cao hơn so với phiên bản hàm đệ quy. Vì khi một hàm được gọi, chương trình sẽ tốn một lượng chi phí cho việc đưa hàm vào ngăn xếp (stack).

Chú ý: Ưu tiên sử dụng vòng lặp thay vì đệ quy.

Kết luận

Qua bài viết này, bạn đã nắm được khái niệm Đệ quy trong C++ (Recursion) và những bài toán cơ bản về đệ quy.

Trong bài tiếp theo, mình sẽ giới thiệu cho các bạn về Khuôn mẫu hàm trong C++ (Function templates).

Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên "Luyện tập - Thử thách - Không ngại khó".

Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần Bình luận bên dưới hoặc trong mục Hỏi & Đáp trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.