Bài 30. Đệ quy trong C – Hàm đệ quy

Hàm đệ quy trong C là các hàm mà bản thân nó có khả năng gọi lại chính nó. Và kỹ thuật này được gọi là đệ quy. Trong bài học này, Lập Trình Không Khó sẽ cùng các bạn đi tìm hiểu về hàm đệ quy, bao gồm: tính chất của hàm đệ quy, ưu điểm và nhược điểm của đệ quy, thực hành các bài toán kinh điển sử dụng đệ quy, tìm hiểu về khái niệm khử đệ quy…

Hàm đệ quy trong C hoạt động ra sao?

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

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

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

Vậy 1 chương trình sẽ chạy như thế nào nếu có hàm đệ quy? Bạn hãy xem hình ảnh dưới đây:

Như các bạn có thể thấy, khi một hàm đệ quy được gọi (ở ví dụ trên là hàm main gọi) thì thay vì hàm đó chỉ được thực thi 1 lần thì ở đây bản thân hàm gọi lại chính nó => Nó có thể tự chạy lại chính mình số lần bất kỳ.

Tính dừng là gì?

Chắc hẳn bạn đang có câu hỏi, hàm đệ quy tự gọi lại chính nó ở mỗi lần chạy; Vậy thì nó chạy không bao giờ dừng à? Để tránh việc lặp vô tận, hàm đệ quy cần có tính dừng: Nếu gặp 1 điều kiện nào đó, nó cần phải dừng lại việc tự gọi lại chính mình. Và tính dừng là điều bắt buộc phải có trong 1 hàm đệ quy trong C cùng như mọi ngôn ngữ khác.

Bạn vui lòng xem video phía trên để thấy rõ hơn về tính dừng của đệ quy. Sau đây, chúng ta sẽ cùng nhau đi 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 ở mỗi ví dụ nhé!

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

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

#include <stdio.h>

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


/*
    Giải thích hàm đệ quy
    Giả sử n = 4
    4 + SumRecursion(3)
    4 + 3 + SumRecursion(2)
    4 + 3 + 2 + SumRecursion(1)
    4 + 3 + 2 + 1 + SumRecursion(0)
    4 + 3 + 2 + 1 + 0
*/

int main(){
    int n;
    printf("nNhap n = ");
    scanf("%d", &n);

    int sum2 = SumRecursion(n);

    printf("nSum1 = %d", sum1);
    printf("nSum2 = %d", sum2);
}

Bài tập này được giải thích chi tiết trên video rồi, do đó mình chỉ làm rõ hai vấn đề ở đây:

• Đệ quy: Hàm `SumRecursion()` đã gọi lại chính nó với 1 tham số khác
• Tính dừng: Khi tham số truyền vào có giá trị là 0 thì sẽ dừng gọi đệ quy => Vì gặp return là thoát hàm mất rồi.
• Giải thích lần lượt các bước gọi hàm, cách hàm thực hiện có trong code và video phía trên.

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

Do đệ quy có tính chất lặp, nên bạn hoàn toàn có thể dùng đệ quy để làm vòng lặp. Ví dụ như sau:

#include <stdio.h>
 
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 count <= 5 sai, hàm sẽ dừng lại. Bởi vì lời gọi đệ quy chỉ được thực hiện khi điều kiện này đúng.
• Việc sử dụng biến static trong C,  bạn sẽ được tìm hiểu rõ nó trong bài học số 32 của khóa học này. Biến static sẽ không bị reset giá trị nên chúng ta có thể dùng nó để đếm.

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

#include <stdio.h>
 
void loop() {
    printf("loopn");
    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 mà số n còn lớn hơn 0, chúng ta sẽ tăng giá trị đếm 1 đơn vị, và sau đó chia nguyên n với 10 để bỏ chữ số cuối của nó.

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

/*
    Vì dụ: a = 9, b = 3
    Vì a * b != 0 => return UCLN(0, 3) // ULCN(9%3, 3)
    Vì a * b == 0 => return a + b = 3
*/
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. Xin chào và hẹn gặp lại cả nhà!