Hàm đệ quy trong C

Hàm đệ quy

Một hàm mà nó có khả năng gọi lại chính bản thân nó. Kỹ thuật này gọi là hàm đệ quy.


Hàm đệ quy hoạt động như thế nào?

void recurse()
{
    ... .. ...
    recurse();
    ... .. ...
}

int main()
{
    ... .. ...
    recurse();
    ... .. ...
}

ham de quy

Hàm đệ quy sẽ tự gọi chính bản thân mình vô số lần cho đến khi gặp một điều kiện nhất định.

Để tránh việc hàm đệ quy tự gọi vô hạn lần, lệnh if..else thường được sử dụng.


Ví dụ: Tính tổng các số tự nhiên bằng đệ quy

#include <stdio.h>
int sum(int n);

int main() {
    int number, result;

    printf("Hãy nhập một số nguyên dương: ");
    scanf("%d", &number);

    result = sum(number);

    printf("sum = %d", result);
    return 0;
}

int sum(int n) {
    if (n != 0)
        // sum() function calls itself
        return n + sum(n-1); 
    else
        return n;
}

Kết quả

Hãy nhập một số nguyên dương: 3
sum = 6

Khởi đầu, sum() được gọi từ hàm main() với number là số được nhập bởi người dùng được gán vào argument của sum(). Vậy ban đầu giá trị n trong sum()3.

Lệnh return n + sum(n-1); sẽ gọi hàm sum() bên trong chính nó với giá trị argument bây giờ là n-1=2. Quá trình tự gọi này xảy ra liên tục cho đến khi n=0.

Khi n=0, lệnh return n; sẽ trả về biến n mà không gọi hàm sum() nữa. Vậy nên quá trình đệ quy kết thúc.

ham de quy hoat dong


Ưu và nhược điểm của đệ quy

Hàm đệ quy làm cho chương trình ngắn gọn và đẹp. Tuy nhiên, các vòng lập đệ quy lại khiến cho chương trình chạy rất chậm.

Series Navigation<< Hàm trong C – phần 3Lớp lưu trữ (Storage Class) trong C – biến local global static >>

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *