Hàm đệ quy trong C++

Được viết bởi: phuongle (SMod)

Bình luận: 0
0 Lượt chia sẻ
Lượt xem

Độ khó

Dễ

Số bước

Thời gian

Chia sẻ

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. Vì vậy trong bài học hôm nay mình sẽ lấy ví dụ đơn giản nhất có sử dụng hàm đệ quy để cho các bạn có thể hiểu một cách dễ dàng nhất.

1. Hàm đệ quy trong C++

Trong C++ một hàm gọi chính nó ta gọi đó là hàm đệ quy.

Cú pháp

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

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.

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++ như sau:

Ví dụ

#include<iostream>  
using namespace std;
int GiaiThua(int n) {
    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 cơ sở

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

Đệ 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. 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é. Cảm ơn các bạn đã theo dõi bài viết này

Theo: freetuts.net