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.

test php

banquyen png

Bài viết này được đăng tại

freetuts.net

Bạn đang đọc: Giải thích về hàm đệ quy trong C++ dễ hiểu nhất

, không được copy dưới mọi hình thức.

Nói về đệ quy thì bạn hoàn toà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 kèm theo 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ì tất cả chúng ta cùng tìm hiểu và khám phá nhé .

Tóm Tắt

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:

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 1 số ít nguyên trong C + + tất 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ố ít 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  
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à hiệu quả sau khi thực thi chương trình trên như sau :

dequy ex JPG

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 những 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 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 hoàn toàn có thể vận dụng giải thuật đệ quy C + + để xử lý, bằng cách bên trong thân hàm sẽ gọi đến chính hàm đó .

Ví dụ

#include  
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:

Xem thêm: Lấy Lại Mật Khẩu Facebook Qua Bạn Bè Khôi Phục 100%

Đố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 yếu tố thành những yếu tố nhỏ hơn cho đến khi đạt được điều kiện kèm theo cơ bản .
Ví dụ trong chương trình giai thừa ở trên, tất cả chúng ta đang xử lý 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 tái diễn liên tục cho đến khi giá trị n đạt đến điều kiện kèm theo cơ sở ( GiaiThua ( 1 ) = 1 ) .
Vậy điều kiện kèm theo cơ sở là gì tất cả chúng ta cùng tìm hiểu và khám phá 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 tất cả chúng ta nên chỉ ra tối thiểu một điều kiện kèm theo để dừng đệ quy, ta gọi điều kiện kèm theo đó là điều kiện kèm theo cơ sở .
Như ở ví dụ trên, điều kiện kèm theo cơ sở là :

if (n == 1)
        return 1;

Nếu hàm đệ quy không có điều kiện kèm theo cơ sở để dừng đệ quy thì chương trình tất cả chúng ta sẽ lặp vô hạn. Vì vậy, muốn xử lý một bài toán bằng hàm đệ quy mà những bạn không tìm ra được điều kiện kèm theo dừng thì tốt nhất những bạn đừng khi nào sử dụng hàm đệ quy nhé, nó chỉ làm cho chương trình tất cả 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 thuần về đệ quy gián tiếp như sau :

Ví dụ

#include 
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à tác dụng 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, những 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ì tất cả chúng ta có 1 số ít loại đệ quy như sau :
Bài tập nâng cao nhất khi sử dụng đệ quy đó là :
Một số bài tập đệ quy cơ bản như :

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é.

Xem thêm: Cách xóa tài khoản Gmail vĩnh viễn trên máy tính, điện thoại đơn giản

Mình cũng không khuyến khích những 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 kinh nghiệm này ở đây nhé. Trong bài học kinh nghiệm tiếp theo tất cả chúng ta sẽ cùng khám phá về khoanh vùng phạm vi sử dụng của biến trong C + +. Các bạn nhớ theo dõi nhé .

Source: https://final-blade.com
Category: Kiến thức Internet

admin

final-blade.com