STARTING
CONTROL STATEMENT
FUNCTION
ARRAY & POINTER
OOP
STL
ITERATORS
OTHER FEATURES
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
MỚI CẬP NHẬT

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, 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:

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

dequy ex JPG

Đố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:

dequy ex JPG

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:

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

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

Cùng chuyên mục:

Kiểm tra chuỗi có phải là chuỗi pangram hay không trong C

Kiểm tra chuỗi có phải là chuỗi pangram hay không trong C

Loại bỏ các từ trùng lặp trong một chuỗi trong C

Loại bỏ các từ trùng lặp trong một chuỗi trong C

Chuyển đổi một số thành chuỗi số tiếng Anh trong C

Chuyển đổi một số thành chuỗi số tiếng Anh trong C

Tìm chuỗi con dài nhất không chứa ký tự trùng lặp trong C

Tìm chuỗi con dài nhất không chứa ký tự trùng lặp trong C

Chuyển đổi số nguyên sang dạng chuỗi và ngược lại trong C

Chuyển đổi số nguyên sang dạng chuỗi và ngược lại trong C

Kiểm tra số nguyên tố và số hoàn hảo trong C

Kiểm tra số nguyên tố và số hoàn hảo trong C

Tính lũy thừa của một số nguyên trong C

Tính lũy thừa của một số nguyên trong C

Tính phần dư của phép chia hai số nguyên trong C

Tính phần dư của phép chia hai số nguyên trong C

Tính tổng, hiệu, tích, thương của hai số nguyên trong C

Tính tổng, hiệu, tích, thương của hai số nguyên trong C

Sử dụng con trỏ để tính tổng các phần tử trong mảng trong C

Sử dụng con trỏ để tính tổng các phần tử trong mảng trong C

Sử dụng con trỏ để đảo ngược một chuỗi trong C

Sử dụng con trỏ để đảo ngược một chuỗi trong C

Sắp xếp một mảng số nguyên sao cho số lẻ nằm trước số chẵn trong C

Sắp xếp một mảng số nguyên sao cho số lẻ nằm trước số chẵn trong C

Sắp xếp một mảng chuỗi theo thứ tự từ điển trong C

Sắp xếp một mảng chuỗi theo thứ tự từ điển trong C

Sắp xếp một mảng số nguyên theo thứ tự tăng dần hoặc giảm dần trong C

Sắp xếp một mảng số nguyên theo thứ tự tăng dần hoặc giảm dần trong C

Tìm phần tử lớn thứ k trong mảng trong C

Tìm phần tử lớn thứ k trong mảng trong C

Xóa phần tử trùng lặp trong mảng trong C

Xóa phần tử trùng lặp trong mảng trong C

Đảo ngược mảng không sử dụng mảng phụ trong C

Đảo ngược mảng không sử dụng mảng phụ trong C

Tìm số lần xuất hiện của một phần tử trong mảng trong C

Tìm số lần xuất hiện của một phần tử trong mảng trong C

Tìm giá trị lớn nhất và nhỏ nhất trong một mảng trong C

Tìm giá trị lớn nhất và nhỏ nhất trong một mảng trong C

Tách chuỗi thành các từ riêng lẻ và in ra màn hình trong C

Tách chuỗi thành các từ riêng lẻ và in ra màn hình trong C

Top