Đệ quy tuyến tính (Linear Recursion) trong C / C++

Trong bài viết này, codehow sẽ giới thiệu đến các bạn hàm đệ quy tuyến tính (Linear Recursion) trong C / C++. Đây là một trong 6 loại hàm đệ quy trong lập trình C / C++, được sử dụng nhiều nhất bởi tính căn bản của nó.

Chúng ta sẽ cùng nhau tìm hiểu về hàm đệ quy tuyến tính là gì? Cách nó hoạt động ra sao. Sau đó mình sẽ đưa ra ví dụ cụ thể sử dụng hàm đệ quy tuyến tính (Linear Recursion) trong C / C++.

Hàm đệ quy tuyến tính (Linear Recursion) trong C / C++ là gì?

Cú pháp:

HamDeQuy(){
    HamDeQuy(); 
}

Ví dụ: Ta có hàm đệ quy tính giai thừa là một hàm đệ quy tuyến tính.

int factorial(int n){
    if(n == 0) return 1;
    return n * factorial(n-1);
}

Cơ chế hoạt động của hàm đệ quy tuyến tính (Linear Recursion) trong C / C++

Như đã nói ở bài viết trước, thì hàm đệ quy sẽ hoạt động dựa trên cơ chế LIFO (Last In First Out). Vậy nên hàm đệ quy tuyến tính trong C / C++ cũng sẽ hoạt động dựa trên cơ chế này.

Để hiểu rõ hơn, mình sẽ lấy ví dụ về hàm tính giai thừa của một số nguyên dương n. Sau đó chạy thử hàm đệ quy cho các bạn xem nhé.

int factorial(int n){
    if(n == 0) return 1;
    return n * factorial(n-1);
}

Bây giờ, giả sử mình muốn tính 5! sử dụng hàm đệ quy tuyến tính trên, khi đó hàm sẽ chạy như thế nào?

Như các bạn thấy trong hình, cứ sau mỗi lần gọi hàm nó sẽ đẩy kết quả vào trong Stack. Đầu tiên là 5 - 4 - 3 - 2 - 1 - 1, khi này hết gọi hàm đệ quy. Sau đó gọi Stack để lấy kết quả, thực hiện lấy từ trên xuống vì dựa vào cơ chế LIFO 1 - 1 - 2 - 3 - 4 - 5.

Kết quả sẽ bằng 1 * 1 * 2 * 3 * 4 * 5 = 120.

Ví dụ sử dụng hàm đệ quy tuyến tính (Linear Recursion) trong C / C++

Trong phần này, mình sẽ thực hiện chương trình tính giải thừa của một số được nhập từ bàn phím. Sử dụng hàm đệ quy tuyến tính để tính toán và hiển thị kết quả ra màn hình.

Đầu tiên chúng ta sẽ viết hàm tính giai thừa, hàm này được tạo theo dạng đệ quy tuyến tính. Điều kiện dừng của hàm là n == 1.

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));
}

Tiếp đến khai báo biến n thuộc kiểu int, sau đó yêu cầu người dùng nhập giá trị cho n.

//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);

Cuối cùng là gọi hàm tính giai thừa và truyền tham số là giá trị vừa nhập bởi người dùng.

//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));

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

Kết luận

Như vậy là chúng ta đã cùng nhau tìm hiểu về hàm đệ quy tuyến tính (Linear Recursion) trong C / C++. Qua bài viết này, mình muốn các bạn nắm vững các kiến thức dưới đây:

• Hàm đệ quy tuyến tính là hàm chỉ có duy nhất một câu lệnh gọi lại chính nó trong thân hàm.
• Hàm đệ quy tuyến tính hoạt động dựa trên cơ chế LIFO.
• Ví dụ hàm tính giai thừa là hàm đệ quy tuyến tính.

Ở bài viết tiếp theo, mình sẽ giới bạn loại hàm đệ quy tiếp theo là hàm đệ quy đuối (Tail Recursion). Các bạn chú ý theo dõi nhé, cảm ơn rất nhiều !!!!