Bài 30. Đệ quy trong C

Hàm đệ quy trong C là một kỹ thuật đặc biệt, cho phép một hàm gọi lại chính nó. Trong bài viết này, chúng ta sẽ khám phá về hàm đệ quy, bao gồm các tính chất, ưu điểm và nhược điểm của nó. Hơn nữa, chúng ta sẽ cùng nhau thực hành các bài toán sử dụng đệ quy và tìm hiểu về khái niệm khử đệ quy.

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

Dưới đây là một chương trình minh họa sử dụng đệ quy trong ngôn ngữ lập trình C. Hãy chú ý, trong thân hàm recurse(), có một lời gọi đệ quy đến chính nó.

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

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

Vậy một chương trình sử dụng đệ quy sẽ chạy như thế nào? Hãy xem hình ảnh dưới đây:

Xem thêm:

Bài tập lập trình với ngôn ngữ C++ - Từ cơ bản đến nâng cao

Hình ảnh minh họa việc sử dụng đệ quy trong lập trình C, nguồn ảnh: programiz.com

Như bạn có thể thấy, khi một hàm đệ quy được gọi (trong ví dụ trên là hàm main()), thay vì chỉ được thực thi một lần, hàm đó có khả năng gọi lại chính nó. Điều này cho phép chương trình tự chạy lại chính mình một số lần tùy ý.

Tính dừng là gì?

Bạn có thể đặt câu hỏi, nếu hàm đệ quy gọi lại chính nó liên tục, liệu nó có bao giờ dừng lại không? Để tránh một vòng lặp vô hạn, hàm đệ quy cần có một điều kiện dừng: khi gặp một điều kiện nào đó, nó sẽ dừng lại việc tự gọi lại chính mình. Điều này được gọi là "tính dừng" và là một yêu cầu bắt buộc trong một hàm đệ quy, không chỉ trong ngôn ngữ C mà còn trong mọi ngôn ngữ lập trình khác.

Bạn có thể xem video phía trên để hiểu rõ hơn về tính dừng trong đệ quy. Tiếp theo, chúng ta sẽ cùng giải các bài tập kinh điển sử dụng đệ quy. Mình sẽ giải thích chi tiết từng ví dụ cho bạn!

Bài tập thực hành đệ quy trong C

BT1. Tính tổng các số từ 1 đến n

#include 

// Hàm đệ quy
int SumRecursion(int n){
    /* sum = 1 + ... + n */
    // Điều kiện dừng
    if(n == 0){
        return 0;
    }
    // Gọi lại chính nó
    return n + SumRecursion(n-1);
}

int main(){
    int n;
    printf("Nhập n = ");
    scanf("%d", &n);
    int sum = SumRecursion(n);
    printf("Tổng = %d", sum);
}

Bài tập này đã được giải thích chi tiết trong video, vì vậy mình chỉ giải thích hai vấn đề ở đây:

Đệ quy: Hàm SumRecursion() gọi lại chính nó với một tham số khác.
Tính dừng: Nếu tham số truyền vào có giá trị là 0, hàm sẽ dừng lại để tránh việc gọi đệ quy vô hạn.

BT2. Xây dựng vòng lặp bằng đệ quy

Do tính chất lặp của đệ quy, bạn hoàn toàn có thể sử dụng đệ quy để thay thế cho vòng lặp. Ví dụ như sau:

#include 

static int count = 0;

void loop() {
    count++;
    if (count = 5) {
        printf("loop %d\n", count);
        loop();
    }
}

int main() {
    loop();
    return 0;
}

Tính dừng: Nếu điều kiện count = 5 sai, hàm sẽ dừng lại. Lời gọi đệ quy chỉ được thực hiện khi điều kiện này đúng.
Biến static: Chúng ta sẽ tìm hiểu về biến static trong bài học số 32 của khóa học này. Biến static không bị reset giá trị, nên chúng ta có thể sử dụng nó để đếm.

Chú ý: Nếu hàm đệ quy không có điều kiện dừng, nó sẽ lặp vô hạn! Bạn có thể chạy thử ví dụ dưới đây:

#include 

void loop() {
    printf("loop\n");
    loop();
}

int main() {
    loop();
    return 0;
}

BT3. Đếm số lượng chữ số của số nguyên dương n

int DigitCount(int n) {
    if(n==0) return 0;
    return 1 + DigitCount(n/10);
}

Giải thích: Chừng nào số n còn lớn hơn 0, chúng ta sẽ tăng giá trị đếm lên 1 đơn vị, sau đó chia nguyên n cho 10 để bỏ đi chữ số cuối cùng.

BT4. Tìm ƯCLN của 2 số nguyên dương

int UCLN(int a, int b) {
    if (a * b == 0)
        return a + b;
    if (a > b)
        return UCLN(a - b, b);
    else
        return UCLN(a, b - a);
}

Các bạn sẽ tiếp tục được thực hành các bài tập về hàm và hàm đệ quy ở những bài học tiếp theo. Chúc bạn thành công và hẹn gặp lại!