C Recursion

C Recursion: Định Nghĩa, Cú Pháp và Ví Dụ

Đệ quy (Recursion) là một khái niệm quan trọng trong lập trình, đặc biệt là trong ngôn ngữ C. Đệ quy xảy ra khi một hàm gọi chính nó để giải quyết một bài toán. Thực hành sử dụng đệ quy có thể giúp cho việc giải quyết một số vấn đề phức tạp trở nên đơn giản và dễ hiểu hơn.

Định Nghĩa

Trong ngôn ngữ lập trình C, đệ quy là một kỹ thuật trong đó một hàm sẽ gọi lại chính nó để thực hiện một tác vụ cụ thể. Đệ quy thường được sử dụng để giải quyết các vấn đề mà có thể được chia nhỏ thành các vấn đề con tương tự.

Cú Pháp

Cú pháp của một hàm đệ quy trong C thường giống như một hàm bình thường, với điểm khác biệt là hàm sẽ gọi chính nó. Một hàm đệ quy thường cần có một hoặc nhiều điều kiện dừng để tránh việc gọi vô hạn.

Cú pháp chung:

returnType functionName(parameters) {
    if (condition) {
        // điều kiện dừng
        return baseCase; 
    } else {
        // gọi chính nó với tham số khác
        return functionName(modifiedParameters); 
    }
}

Ví Dụ

1. Tính giai thừa:

Giai thừa của một số nguyên n (ký hiệu là n!) là tích của tất cả các số nguyên dương từ 1 đến n. Giai thừa có thể được tính bằng công thức:

n! = n * (n - 1)!

Hàm đệ quy tính giai thừa có thể được viết như sau:

#include 

int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1; // Điều kiện dừng
    } else {
        return n * factorial(n - 1); // Gọi hàm đệ quy
    }
}

int main() {
    int num;
    printf("Nhập một số nguyên dương: ");
    scanf("%d", &num);
    printf("Giai thừa của %d là: %d\n", num, factorial(num));
    return 0;
}

2. Tìm số Fibonacci:

Chuỗi Fibonacci là một chuỗi số trong đó mỗi số là tổng của hai số trước đó. Số Fibonacci thứ n có thể được tính như sau:

F(n) = F(n-1) + F(n-2)

Hàm đệ quy để tính số Fibonacci:

#include 

int fibonacci(int n) {
    if (n == 0) {
        return 0; // Điều kiện dừng
    } else if (n == 1) {
        return 1; // Điều kiện dừng
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2); // Gọi hàm đệ quy
    }
}

int main() {
    int num;
    printf("Nhập chỉ số Fibonacci: ");
    scanf("%d", &num);
    printf("Số Fibonacci tại chỉ số %d là: %d\n", num, fibonacci(num));
    return 0;
}

Kết Luận

Đệ quy là một công cụ mạnh mẽ trong lập trình C, cho phép người lập trình giải quyết các bài toán phức tạp một cách hiệu quả và trực quan. Tuy nhiên, cần cẩn thận với các điều kiện dừng để tránh rơi vào vòng lặp vô hạn. Với những ví dụ trên, hy vọng bạn đã hiểu rõ hơn về khái niệm và cách sử dụng đệ quy trong ngôn ngữ lập trình C.