Nội dung chính
Đệ quy là gì?
Đệ quy trong C là quá trình trong đó một phương thức gọi lại chính nó một cách liên tiếp. Một phương thức trong C gọi lại chính nó được gọi là phương thức đệ quy.
Cú pháp:
kieu_tra_ve tenhamdequi() {
// your code
tenhamdequi(); /* goi lai chinh no */
}
int main() {
tenhamdequi();
}
Ngôn ngữ lập trình C hỗ trợ đệ quy, ví dụ, một hàm có thể gọi đến chính nó. Nhưng khi bạn sử dụng hàm đệ quy, lập trình viên cần phải cẩn thận định nghĩa điều kiện thoát khỏi hàm, phòng khi gặp phải vòng lặp vô hạn.
Hàm đệ quy rất hữu dụng để giải quyết các vấn đề trong toán học như tính toán giai thừa, tạo dãy Fibonacci, …
Bài tập Đệ quy trong C
Dưới đây là các bài tập C giúp bạn hiểu kiến thức cơ bản về Đệ quy trong C:
Tính dãy số Fibonacci sử dụng đệ quy
Ví dụ chương trình C tìm 10 số Fibonacci đầu tiên sử dụng phương pháp đệ quy:
/**
* Tinh day so Fibonacci bang phuong phap de quy
*
* @author viettuts.vn
*/
#include<stdio.h>
/**
* Tinh so Fibonacci thu n
*
* @param n: chi so cua so Fibonacci tinh tu 0
* vd: F0 = 0, F1 = 1, F2 = 1, F3 = 2
* @return So Fibonacci thu n
*/
int fibonacci(int n) {
if (n < 0) {
return -1;
} else if (n == 0 || n == 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
/**
* Ham main
*/
int main() {
int i;
printf("10 so dau tien cua day so Fibonacci: \n");
for (i = 0; i < 10; i++) {
printf("%d ", fibonacci(i));
}
}
Chạy chương trình C trên cho kết quả như sau:
Tính giai thừa sử dụng đệ quy
Ví dụ chương trình tính giai thừa trong C có sử dụng phương pháp đệ quy:
/**
* Tinh giai thua su dung phuong phap de quy
*
* @author viettuts.vn
*/
#include<stdio.h>
/**
* tinh giai thua
*
* @author viettuts.vn
* @param n: so nguyen duong
* @return giai thua cua so n
*/
long tinhGiaithua(int n) {
if (n > 0) {
return n * tinhGiaithua(n - 1);
} else {
return 1;
}
}
/**
* Ham main
*/
int main() {
int a = 5;
int b = 0;
int c = 10;
printf("Giai thua cua %d la: %d \n", a, tinhGiaithua(a));
printf("Giai thua cua %d la: %d \n", b, tinhGiaithua(b));
printf("Giai thua cua %d la: %d", c, tinhGiaithua(c));
}
Chạy chương trình C trên cho kết quả như sau:
Tìm USCLN và BSCNN của 2 số a và b sử dụng đệ quy
Ví dụ dưới đây sử dụng giải thuật Euclid để giải quyết bài toán tìm ước số chung lớn nhất (USCLN) và bội số chung nhỏ nhất (BSCNN) của hai số nguyên dương a và b:
/**
* Chuong trinh tim uoc chung lon nhat (USCLN)
* va boi so chung nho nhat (BSCNN) cua 2 so a và b
*
* @author viettuts.vn
*/
#include<stdio.h>
/**
* Tim uoc so chung lon nhat (USCLN)
*/
int USCLN(int a, int b) {
if (b == 0) return a;
return USCLN(b, a % b);
}
/**
* Tim boi so chung nho nhat (BSCNN)
*/
int BSCNN(int a, int b) {
return (a * b) / USCLN(a, b);
}
/**
* Ham main
*/
int main() {
int a, b;
printf("Nhap so nguyen duong a = ");
scanf("%d", &a);
printf("Nhap so nguyen duong b = ");
scanf("%d", &b);
// tinh USCLN cua a và b
printf("\nUSCLN cua %d va %d la: %d", a, b, USCLN(a, b));
// tinh BSCNN cua a và b
printf("\nUSCLN cua %d va %d la: %d", a, b, BSCNN(a, b));
}
Chạy chương trình C trên cho kết quả như sau:
Tính tổng n số sử dụng đệ quy
Ví dụ chương trình tổng của n số trong C có sử dụng phương pháp đệ quy:
/**
* Chuong trinh tong cua n so tu nhien
*
* @author viettuts.vn
*/
#include<stdio.h>
int calculateSum(int);
int main() {
int i, num;
int result;
printf("Nhap mot so bat ky: ");
scanf("%d", &num);
result = calculateSum(num);
printf("\nTong cac so tu 1 toi %d la: %d", num, result);
return (0);
}
int calculateSum(int num) {
int res;
if (num == 1) {
return (1);
} else {
res = num + calculateSum(num - 1);
}
return (res);
}
Chạy chương trình C trên cho kết quả như sau:
Bài toán Tháp Hà Nội (Tower of Hanoi) sử dụng đệ quy
Trước khi tìm hiểu lời giải cho bài toán Tháp Hà Nội (Tower of Hanoi), mình xin nhắc lại một số qui tắc của trò chơi toán Tháp Hà Nội này:
Tháp Hà Nội (Tower of Hanoi) là gì ?
Bài toán Tháp Hà Nội (Tower of Hanoi) là một trò chơi toán học bao gồm 3 cột và với số đĩa nhiều hơn 1.
Dưới đây là hình minh họa bài toán Tháp Hà Nội (Tower of Hanoi) với trường hợp có 3 đĩa.
Các đĩa có kích cỡ khác nhau và xếp theo tự tự tăng dần về kích cỡ từ trên xuống: đĩa nhỏ hơn ở trên đĩa lớn hơn. Với số đĩa khác nhau thì ta có các bài toán Tháp Hà Nội (Tower of Hanoi) khác nhau, tuy nhiên lời giải cho các bài toán này là tương tự nhau. Lời giải tối ưu cho bài toán Tháp Hà Nội (Tower of Hanoi) là khi trò chơi chỉ có 3 cọc. Với số cọc lớn hơn thì lời giải bài toán vẫn chưa được khẳng định.
Qui tắc trò chơi toán học Tháp Hà Nội (Tower of Hanoi)
Nhiệm vụ của trò chơi là di chuyển các đĩa có kích cỡ khác nhau sang cột khác sao cho vẫn đảm bảo thứ tự ban đầu của các đĩa: đĩa nhỏ nằm trên đĩa lớn. Dưới đây là một số qui tắc cho trò chơi toán học Tháp Hà Nội (Tower of Hanoi):
- Mỗi lần chỉ có thể di chuyển một đĩa từ cột này sang cột khác.
- Chỉ được di chuyển đĩa nằm trên cùng (không được di chuyển các đĩa nằm giữa).
- Đĩa có kích thước lớn hơn không thể được đặt trên đĩa có kích thước nhỏ hơn.
Dưới đây là hình minh họa cách giải bài toán Tháp Hà Nội (Tower of Hanoi) với trường hợp có 3 đĩa.
Bài toán Tháp Hà Nội (Tower of Hanoi) với số đĩa là n có thể được giải với số bước tối thiểu là 2n−1. Do đó, với trường hợp 3 đĩa, bài toán Tháp Hà Nội (Tower of Hanoi) có thể được giải sau 23−1 = 7 bước.
Chương trình C: sử dụng đệ quy
Dưới đây là chương trình C để giải bài toán Tháp Hà Nội (Tower of Hanoi) sử dụng đệ quy trong C trong C:
/**
* Chuong trinh giai bai toan Thap Ha Noi
*
* @author viettuts.vn
*/
#include<stdio.h>
void TOH(int num, char x, char y, char z);
int main() {
int num;
printf("\nNhap so dia: ");
scanf("%d", &num);
TOH(num - 1, 'A', 'B', 'C');
return (0);
}
void TOH(int num, char x, char y, char z) {
if (num > 0) {
TOH(num - 1, x, z, y);
printf("\n%c -> %c", x, y);
TOH(num - 1, z, y, x);
}
}
Chạy chương trình C trên cho kết quả như sau:
