Hàm đệ quy là gì? Các loại hàm đệ quy trong C / C++

Trong bài viết này, codehow sẽ giới thiệu đến các bạn hàm đệ quy là gì? các loại hàm đệ quy trong C / C++. Đây là một khái niệm khá lạ đối với các bạn mới bắt đầu học lập trình, tuy nhiên đừng vội lo lắng nhé. Serries cấu trúc dữ liệu và giải thuật của codehow sẽ giúp các bạn hiểu rõ hơn về nó.

Chúng ta sẽ cùng nhau tìm hiểu về khái nhiệm hàm đệ quy là gì? Cách thức nó hoạt động và có bao nhiêu loại hàm đệ quy trong C / C++. Bây giờ hãy bắt đầu cùng mình thôi nhé.

Hàm đệ quy là gì?

Cú pháp:

HamDeQuy(){
    HamDeQuy(); //gọi lại chính nó
}

Như các bạn đã thấy thì trong cú pháp, HamDeQuy() thực hiện gọi chính nó trong thân hàm. Một hàm tương tự như vậy được gọi là hàm đệ quy.

Hàm đệ quy trong C / C++ cũng tương tự như các vòng lặp, nó cũng phải cần xác định được điểm dừng. Nếu không xác định được điểm dừng sẽ dẫn đến tình trạng lặp vô hạn (Stack Overhead).

Mình sẽ lấy ví dụ tính giai thừa để minh họa cho việc sử dụng hàm đệ quy nhé.

Ví dụ: Chúng ta cần tính giai thừa của số nguyên 5.

5! = 5 * 4!
4! = 4 * 3!
…
1! = 1 * 0!

Dựa vào quy luật trên, ta có công thức tính giai thừa của một số nguyên n.

n! = n * (n-1)!

Đối với công thức trên, ta thấy nếu n = 0 hoặc = 1 thì kết quả tính giai thừa luôn bằng 1. Vì vậy đây chính là điểm dừng của hàm đệ quy.

Áp dụng công thức trên, chúng ta có hàm đệ quy tính giai thừa của một số nguyên dương n trong C / C++ như sau:

int giaiThua(int n){
    if(n<=1) return 1;
    return n * giaiThua(n-1);
}

Dưới đây là hai chương trình tính giai thừa của số nguyên dương n, các bạn có thể tham khảo nhé. Mình đã viết bằng hai ngôn ngữ khác nhau là C và C++.

Chương trình C:

#include <stdio.h>

int GiaiThua(int n) {
    // Trường hợp người dùng nhập n == 1 thì thoát khỏi đệ quy
    if (n == 1)
        return 1;
    else
    //ngược lại thì gọi hàm đệ quy với tham số n - 1
        return (n * GiaiThua(n - 1));
}
 

int main(void) {
  //khai báo biến n là số cần tính giai thừa
    int n;
  //yêu cầu người dùng nhập vào số n cần tính giai thừa
    printf("Nhập số nguyên dượng n cần tính giai thừa: ");
    scanf("%d", &n);
    //hiển thị kết quả sau khi tính bằng cách gọi hàm tính giai thừa
    printf("Giai thừa của %d là: %d",n,GiaiThua(n));

    printf("\n---------------------------------\n");
    printf("Chương trình này được đăng tại codehow.net");
    return 0;  
}

Kết quả:

Chương trình C++:

#include<iostream>  
using namespace std;
int GiaiThua(int n) {
    // Trường hợp người dùng nhập n == 1 thì thoát khỏi đệ quy
    if (n == 1)
        return 1;
    else
    //ngược lại thì gọi hàm đệ quy với tham số n - 1
        return (n * GiaiThua(n - 1));
}
 
int main()   
{    
  //khai báo biến n là số cần tính giai thừa
    int n;
  //yêu cầu người dùng nhập vào số n cần tính giai thừa
    cout << "Nhập số nguyên dượng n cần tính giai thừa: ";
    cin >> n;
    //hiển thị kết quả sau khi tính bằng cách gọi hàm tính giai thừa
    cout << "Giai thừa của " << n << " là: " << GiaiThua(n) << endl;

    cout<<"\n---------------------------------\n";
    cout<<"Chương trình này được đăng tại codehow.net";
    return 0;  
}

Kết quả:

Cơ chế hoạt động của hàm đệ quy trong C / C++

Để mình lấy một ví dụ thực tế trong cuộc sống để các bạn dễ hình dung nhé.

Ví dụ: Giả sử chúng ta bỏ từng gói mì vào thùng trước, sau đó dùng keo dán thùng lại. Vậy đến khi muốn lấy mì, ta phải tháo keo trên thùng ra, khi đó mới có thể lấy mì trong thùng.

Đây là cơ chế hoạt động chung của hàm đệ quỵ trong C / C++, mỗi loại hàm đệ quy sẽ hoạt động riêng theo một quy luật khác nhau. Ở các bài viết tiếp theo, mình sẽ giải thích từng loại hàm đệ quy nhé.

Kết luận: Hàm đệ quy hoạt động dựa vào cơ chế LIFO (Last In First Out).

Các loại hàm đệ quy trong C / C++

Trong lập trình C / C++, chúng ta có 6 loại hàm đệ quy cơ bản dưới đây.

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

Mỗi hàm đệ quy có một quy luật hoạt động riêng, đó là điểm đặc trưng của từng loại.

Có một bài toán nổi tiếng áp dụng thuật toán đệ quy để giải đó chính là "bài toán tháp Hà Nội". Mình sẽ hướng dẫn giải bài toán cụ thể ở một bài viết khác, các bạn nhớ chú ý theo dõi nhé.

Ngoài ra còn có một số bài toán khác như: Chuỗi Fibonanci, Giai thừa, ... .

Kết luận

Như vậy là chúng ta đã cùng nhau tìm hiểu về hàm đệ quy là gì? Các loại hàm đệ quy trong C / C++. Qua bài viết, các bạn chỉ cần lưu ý cho mình ba kiến thức.

• Điểm dừng của hàm đệ quy.
• Cơ chế hoạt động của hàm đệ quy (LIFO).
• Các loại hàm đệ quy trong C / C++.

Cảm ơn các bạn rất nhiều, hẹn gặp lại các bạn ở bài viết khác nhé !!