Giải Thích Về Hàm đệ Quy Trong C++ Dễ Hiểu Nhất

Trong bài học hôm nay chúng ta sẽ tìm hiểu về hàm đệ quy trong C++, đây là nội dung mà mình nghĩ là tương đối khó đối với các bạn mới bắt đầu học lập trình.

Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

Nói về đệ quy thì bạn có thể liên tưởng đến khái niệm vòng lặp trong lập trình, nghĩa là một chương trình sẽ được gọi lại nhiều lần cho đến khi điều kiện dừng được kích hoạt. Tuy nhiên, nếu so sánh giữa vòng lặp và đệ quy thì đệ quy sẽ tốn tài nguyên để biên dịch hơn. Chi tiết thế nào thì chúng ta cùng tìm hiểu nhé.

1. Hàm đệ quy trong C++ là gì?

Trong C++, một hàm gọi chính nó ta gọi đó là hàm đệ quy, nghĩa là trong thân hàm sẽ gọi đến chính tên hàm hiện tại và truyền đúng những tham số mà hàm đã khai báo.

Cú pháp: Cú pháp của hàm đệ quy trong C++ như sau:

Bài viết này được đăng tại [free tuts .net]

Cú pháp HamDeQuy(){ HamDeQuy(); //goi lai chinh no }

Ví dụ: Chúng ta cùng xem một ví dụ đơn giản về hàm đệ quy trong C++ đó là tính giai thừa của một số nguyên.

Trước khi giải bài toán tính giai thừa của một số nguyên trong C++ chúng ta cùng nhớ lại công thức tính giai thừa trong toán học trước đã nhé.

Theo định nghĩa giai thừa ta có:

• 0! = 1
• n! = 1 * 2 * 3 * … * n

Vậy là ta đã có công thức tính giai thừa của một số nguyên rồi. Nếu n = 0 thì giai thừa bằng 1. Nếu n > 0 thì giai thừa sẽ là tích từ 1 đến n. Và không có giai thừa của số âm.

Giải bằng vòng lặp For

Trước khi đi vào giải bài toán trên bằng hàm đệ quy, mình sẽ giải bằng vòng lặp for trong C++ trước nhé.

Ví dụ #include<iostream> using namespace std; int main() { int n; while(true) { int giaithua = 1; cout << "Nhap so n: "; cin >> n; //Nhap n nho hon 0 de thoat khoi vong lap if(n < 0) { cout << " So am khong co giai thua" << endl; break; } if ( n > 0) { for(int i = 1; i <=n; i++) { giaithua = giaithua * i; } } cout << " Giai thua cua " << n << " la: " << giaithua << endl; } return 0; }

Và kết quả sau khi thực thi chương trình trên như sau:

Như vậy, để giải quyết bài toán giai thừa của một số bằng vòng lặp for trong C++ rất đơn giản phải không các bạn? Bây giờ mình sẽ giải bài toán giai thừa trên bằng hàm đệ quy trong C++.

Giải bằng đệ quy C++

Các bạn để ý kỹ thì thấy thuật toán tính giai thừa sẽ như sau: Giả sử cần tính 5!, lúc này quy luật của nó sẽ là.

• 5! = 4! * 5
• 4! = 3! * 4
• 3! = 2! * 3
• 2! = 1! * 2
• 1! = 1

Thay các vế vào ta sẽ được quy luật: 5! = 1 * 2 * 3 * 4 * 5.

Giả sử ta có hàm tính gian thừa của một số tên là GT, lúc này thay vào công thức trên ta được như sau:

• GT(5) = GT(4) * 5
• GT(4) = GT(3) * 4
• GT(3) = GT(2) * 3
• GT(2) = GT(1) * 2
• GT(1) = 1

Vậy, ta có thể áp dụng giải thuật đệ quy C++ để giải quyết, bằng cách bên trong thân hàm sẽ gọi đến chính hàm đó.

Ví dụ #include<iostream> using namespace std; int GiaiThua(int n) { // Trường hợp người dùng nhập if (n == 1) return 1; else return (n * GiaiThua(n - 1)); } int main() { int n; while(true) { cout << "Nhap so n: "; cin >> n; //Nhap n nho hon 0 de thoat khoi vong lap if(n < 0) { cout << " So am khong co giai thua" << endl; break; } cout << " Giai thua cua " << n << " la: " << GiaiThua(n) << endl; } return 0; }

Và kết quả sau khi thực thi chương trình trên như sau:

Đối với các bạn mới bắt đầu học lập trình thì cách giải bài toán giai thừa trên bằng vòng lặp for sẽ dễ hiểu hơn rất nhiều so với việc giải bằng hàm đệ quy. Tuy nhiên, các bạn đừng quá lo lắng, mình sẽ giải thích đoạn code cho các bạn bạn dễ hiểu.

Giả sử mình nhập n = 5 thì chương trình trên sẽ chạy như sau:

GiaiThua(5) GiaiThua(4) GiaiThua(3) GiaiThua(2) GiaiThua(1) return 1 return 2*1 = 2 return 3*2 = 6 return 4*6 = 24 return 5*24 = 120

Mục đích của hàm đệ quy là chia vấn đề thành các vấn đề nhỏ hơn cho đến khi đạt được điều kiện cơ bản.

Ví dụ trong chương trình giai thừa ở trên, chúng ta đang giải quyết hàm giai thừa GiaiThua(n) bằng cách gọi hàm giai thừa nhỏ hơn GiaiThua(n-1), điều này được lặp lại liên tục cho đến khi giá trị n đạt đến điều kiện cơ sở (GiaiThua(1) = 1).

Vậy điều kiện cơ sở là gì chúng ta cùng tìm hiểu trong nội dung tiếp theo nhé.

2. Điều kiện dừng đệ quy C++ rất quan trọng

Trong hàm đệ quy chúng ta nên chỉ ra ít nhất một điều kiện để dừng đệ quy, ta gọi điều kiện đó là điều kiện cơ sở.

Như ở ví dụ trên, điều kiện cơ sở là:

if (n == 1) return 1;

Nếu hàm đệ quy không có điều kiện cơ sở để dừng đệ quy thì chương trình chúng ta sẽ lặp vô hạn. Vì vậy, muốn giải quyết một bài toán bằng hàm đệ quy mà các bạn không tìm ra được điều kiện dừng thì tốt nhất các bạn đừng bao giờ sử dụng hàm đệ quy nhé, nó chỉ làm cho chương trình chúng ta bị lập vô tận mà thôi.

3. Đệ quy trực tiếp và đệ quy gián tiếp C++

Đệ quy trực tiếp: Khi hàm gọi chính nó, nó được gọi là đệ quy trực tiếp, ví dụ chúng ta đã thấy ở trên là một ví dụ đệ quy trực tiếp.

Đệ quy gián tiếp: Khi hàm gọi hàm khác và hàm đó lại gọi lại hàm gọi, thì đây được gọi là đệ quy gián tiếp. Ví dụ: hàm A gọi hàm B và hàm B lại gọi lại hàm A.

Chúng ta cùng xem một ví dụ đơn giản về đệ quy gián tiếp như sau:

Ví dụ #include <iostream> using namespace std; int GiaiThua1(int); int GiaiThua2(int); int GiaiThua1(int n){ if(n==0) return 1; else return n*GiaiThua2(n-1); } int GiaiThua2(int n){ if(n==0) return 1; else return n*GiaiThua1(n-1); } int main(){ int n; while(true) { cout << "Nhap so n: "; cin >> n; //Nhap n nho hon 0 de thoat khoi vong lap if(n < 0) { cout << " So am khong co giai thua" << endl; break; } cout << " Giai thua cua " << n << " la: " << GiaiThua1(n) << endl; } return 0; }

Và kết quả sau khi thực thi đoạn code trên như sau:

Nhìn chương trình rất là rất rối, các bạn hạn chế sử dụng đệ quy gián tiếp kiểu cũng như đệ quy trực tiếp nhé.

4. Một số loại đệ quy C++ thường gặp

Trong lập trình nói chung và trong C++ nói riêng thì chúng ta có một số loại đệ quy như sau:

• Đệ quy tuyến tính
• Đệ quy đuôi
• Đệ quy nhị phân
• Đệ quy đa tuyến
• Đệ quy lồng
• Đệ quy tương hỗ

Bài tập nâng cao nhất khi sử dụng đệ quy đó là:

• Bài toán tháp Hà Nội

Một số bài tập đệ quy cơ bản như:

• Chuỗi Fibonacci

5. Kết luận

Vậy là trong bài học hôm nay chúng ta đã tìm hiểu xong về hàm đệ quy trong C++ là gì rồi. Trong bài học hôm nay chỉ cần các bạn nhớ một điều là khi sử dụng hàm đệ quy thì chắc chắn rằng hàm đệ quy đó phải có ít nhất một điều kiện dừng nhé.

Mình cũng không khuyến khích các bạn sử dụng hàm đệ quy trong chương trình của mình vì nó làm cho chương trình của bạn rối thêm mà thôi.

Vậy mình sẽ kết thúc bài học này ở đây nhé. Trong bài học tiếp theo chúng ta sẽ cùng tìm hiểu về phạm vi sử dụng của biến trong C++. Các bạn nhớ theo dõi nhé.