Đệ 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.
Sử dụng đệ quy giúp code chặt chẽ hơn nhưng sẽ khó để hiểu hơn.
Cú pháp:
kieu_tra_ve tenhamdequi() {
// your code
tenhamdequi(); /* goi lai chinh no */
}
int main() {
tenhamdequi();
}
Nội dung chính
Ví dụ về đệ quy trong C
Dưới đây là các ví dụ về cách sử dụng đệ quy trong C.
Ví dụ 1: vòng lặp vô tận
#include <stdio.h>
void p() {
printf("hello\n");
p();
}
int main() {
p();
return 0;
}
Kết quả:
hello hello ... Lỗi tràn bộ nhớ...
Ví dụ 2: vòng lặp có hạn
#include <stdio.h>
static int count = 0;
void p() {
count++;
if (count <= 5) {
printf("hello %d \n", count);
p();
}
}
int main() {
p();
return 0;
}
Kết quả:
hello 1 hello 2 hello 3 hello 4 hello 5
Ví dụ 3: tính giai thừa
#include <stdio.h>
int factorial(int n) {
if (n == 1)
return 1;
else
return (n * factorial(n - 1));
}
int main() {
printf("Giai thua cua 5 la: %d", factorial(5));
return 0;
}
Kết quả:
Giai thừa của 5 là: 120
Chương trình trên hoạt động như sau:
factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)
return 1
return 2*1 = 2
return 3*2 = 6
return 4*6 = 24
return 5*24 = 120
Ví dụ 4: dẫy số Fibonacci
#include <stdio.h>
static int n1 = 0, n2 = 1, n3 = 0;
void printFibo(int count) {
if (count > 0) {
n3 = n1 + n2;
n1 = n2;
n2 = n3;
printf(" %d", n3);
printFibo(count - 1);
}
}
int main() {
int count = 15;
printf("%d %d", n1, n2); // in 0 và 1
printFibo(count - 2); // n-2 vì 2 so 0 và 1 da duoc in ra
return 0;
}
Kết quả:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377