Tổng hợp một số bài tập về Đệ quy trong ngôn ngữ lập trình C

Đệ quy - Khám phá quá trình gọi lại chính mình

Đệ quy trong ngôn ngữ lập trình C là một quá trình mà một phương thức gọi lại chính nó một cách liên tiếp. Khi một phương thức gọi lại chính nó, ta gọi đó là phương thức đệ quy.

Ngôn ngữ lập trình C hỗ trợ đệ quy, cho phép một hàm gọi chính nó. Tuy nhiên, khi sử dụng hàm đệ quy, chúng ta cần đặc biệt lưu ý định nghĩa điều kiện thoát khỏi hàm, để tránh rơi vào vòng lặp vô hạn.

Hàm đệ quy rất hữu ích để giải quyết các vấn đề trong toán học, chẳng hạn như tính toán giai thừa hay tạo dãy Fibonacci.

Bài tập Đệ quy trong ngôn ngữ lập trình C

Dưới đây là một số bài tập trong ngôn ngữ lập trình C giúp bạn hiểu về đệ quy:

Tính dãy số Fibonacci sử dụng đệ quy

Dưới đây là một ví dụ về chương trình C sử dụng đệ quy để tính 10 số Fibonacci đầu tiên:

#include 

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n-1) + fibonacci(n-2);
}

int main() {
    int n = 10;
    for (int i = 0; i < n; i++) {
        printf("%d ", fibonacci(i));
    }
    return 0;
}

Kết quả khi chạy chương trình C trên sẽ là:

0 1 1 2 3 5 8 13 21 34

Tính giai thừa sử dụng đệ quy

Dưới đây là một ví dụ chương trình C sử dụng đệ quy để tính giai thừa:

#include 

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

int main() {
    int n = 5;
    printf("Giai thua cua %d la %d", n, factorial(n));
    return 0;
}

Kết quả khi chạy chương trình C trên sẽ là:

Giai thua cua 5 la 120

Tìm ước số chung lớn nhất (USCLN) và bội số chung nhỏ nhất (BSCNN) sử dụng đệ quy

Dưới đây là một ví dụ sử dụng giải thuật Euclid để tìm USCLN và BSCNN của hai số nguyên dương a và b:

#include 

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

int main() {
    int a = 12;
    int b = 18;
    printf("USCLN cua %d va %d la %d\n", a, b, gcd(a, b));
    printf("BSCNN cua %d va %d la %d\n", a, b, lcm(a, b));
    return 0;
}

Kết quả khi chạy chương trình C trên sẽ là:

USCLN cua 12 va 18 la 6
BSCNN cua 12 va 18 la 36

Tính tổng n số sử dụng đệ quy

Dưới đây là một ví dụ chương trình C sử dụng đệ quy để tính tổng của n số:

#include 

int sum(int n) {
    if (n == 1) {
        return 1;
    }
    return n + sum(n-1);
}

int main() {
    int n = 5;
    printf("Tong cua %d so dau tien la %d", n, sum(n));
    return 0;
}

Kết quả khi chạy chương trình C trên sẽ là:

Tong cua 5 so dau tien la 15

Bài toán Tháp Hà Nội (Tower of Hanoi)

Trước khi tìm hiểu lời giải cho bài toán Tháp Hà Nội, hãy cùng nhau tìm hiểu một số qui tắc của trò chơi này.

Tháp Hà Nội - Một trò chơi toán học thú vị

Bài toán Tháp Hà Nội là một trò chơi toán học bao gồm 3 cột và một số đĩa. Các đĩa có kích cỡ khác nhau và được xếp theo thứ tự từ nhỏ đến lớn lên các cột.

Mục tiêu của trò chơi là di chuyển tất cả các đĩa từ cột xuất phát sang cột đích, qua một cột trung gian, sao cho vẫn giữ được thứ tự ban đầu của các đĩa.

Qui tắc của bài toán Tháp Hà Nội

Bài toán Tháp Hà Nội tuân theo các qui tắc sau:

• Mỗi lần chỉ được di chuyển một đĩa từ một cột sang một cột khác.
• Chỉ được di chuyển đĩa nằm trên cùng của mỗi cột. Không được di chuyển các đĩa nằm phía dưới đĩa đang xét.
• Đĩa có kích thước lớn hơn không thể được đặt lên đĩa có kích thước nhỏ hơn.

Chương trình C giải bài toán Tháp Hà Nội

Dưới đây là chương trình C giải bài toán Tháp Hà Nội sử dụng đệ quy:

#include 

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
    if (n == 1) {
        printf("Chuyen dia 1 tu cot %c sang cot %c\n", from_rod, to_rod);
        return;
    }
    towerOfHanoi(n-1, from_rod, aux_rod, to_rod);
    printf("Chuyen dia %d tu cot %c sang cot %c\n", n, from_rod, to_rod);
    towerOfHanoi(n-1, aux_rod, to_rod, from_rod);
}

int main() {
    int n = 3;
    towerOfHanoi(n, 'A', 'C', 'B');
    return 0;
}

Kết quả khi chạy chương trình C trên sẽ hiển thị cách di chuyển các đĩa từ cột A sang cột C theo qui tắc của bài toán Tháp Hà Nội.

Bài toán Tháp Hà Nội với số đĩa n có thể được giải trong 2n−1 bước. Với trường hợp 3 đĩa, bài toán có thể giải sau 23−1 = 7 bước.

Đó là một số bài tập về đệ quy trong ngôn ngữ lập trình C. Hy vọng qua bài viết này, bạn đã nhận thấy tính hữu ích của đệ quy trong việc giải quyết các vấn đề toán học trong ngôn ngữ lập trình C.