Đệ quy trong C++
1. Khái niệm
Đệ 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 hàm 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.
2. Cú pháp
|
kieu_tra_ve ten_ham() {
// code
ten_ham();
}
|
3. Ví dụ về đệ quy trong C++
Ví dụ 1: vòng lặp vô tận
|
#include <iostream>
using namespace std;
void p() {
cout << "hello" << endl;
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 <iostream>
using namespace std;
static int count = 0;
void p() {
count++;
if (count <= 5) {
cout << "hello" << count << endl;
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 <iostream>
using namespace std;
int factorial(int n) {
if (n == 1)
return 1;
else
return (n * factorial(n - 1));
}
int main() {
cout << "Giai thua cua 5 la:" << 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 <iostream>
using namespace std;
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;
cout << 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
XEM THÊM: Mảng (array) trong C++