Giới thiệu
Bạn đã từng nghe về đệ quy trong lập trình C++ chưa? Trong bài viết trước, chúng ta đã tìm hiểu về con trỏ hàm trong C++. Hôm nay, mình sẽ giới thiệu đến các bạn khái niệm đệ quy trong C++.
Nội dung
Để hiểu rõ bài viết này, bạn nên có kiến thức cơ bản về hàm và giá trị trả về trong C++.
Trong bài viết này, mình sẽ giới thiệu các vấn đề sau:
- Đệ quy là gì?
- Điều kiện dừng (điều kiện cơ sở)
- Một số bài toán đệ quy kinh điển
- Đệ quy so với vòng lặp
Đệ quy là gì?
Một hàm được gọi là đệ quy nếu bên trong thân hàm có một lời gọi đến chính nó. Hàm đệ quy luôn có điều kiện dừng được gọi là "điểm neo". Khi đạt tới điểm neo, hàm sẽ không gọi chính nó nữa.
Khi được gọi, hàm đệ quy thường được truyền một tham số, thường là kích thước của bài toán ban đầu. Sau mỗi lần gọi đệ quy, tham số sẽ nhỏ dần, nhằm phản ánh bài toán đã nhỏ hơn và đơn giản hơn. Khi tham số đạt tới một giá trị cực tiểu (tại điểm neo), hàm sẽ chấm dứt.
Ví dụ:
#include
using namespace std;
void countDown(int count) {
cout << "push " << count << '\n';
countDown(count - 1); // countDown() tự gọi lại chính nó
}
int main() {
countDown(3);
return 0;
}
// Output:
// push 3
// push 2
// push 1
Trong chương trình trên, khi countDown(3)
được gọi, thì "push 3" được in ra và countDown(2)
được gọi. Sau đó countDown(2)
in "push 2" và gọi countDown(1)
. Sau đó countDown(1)
in "push 1" và gọi countDown(0)
. Việc này được lặp lại vô hạn, đây là một hàm đệ quy lặp vô hạn.
Điều kiện dừng (điều kiện cơ sở)
Hàm đệ quy phải có một điều kiện kết thúc đệ quy, nếu không chương trình sẽ lặp vô hạn (đến khi tràn bộ nhớ ngăn xếp). Điều kiện dừng của hàm đệ quy được gọi là điều kiện cơ sở.
Ví dụ:
#include
using namespace std;
void countDown(int count) {
cout << "push " << count << '\n';
if (count > 1) // điều kiện dừng
countDown(count - 1);
cout << "pop " << count << '\n';
}
int main() {
countDown(3);
return 0;
}
// Output:
// push 3
// push 2
// push 1
// pop 1
// pop 2
Trong chương trình trên, do có điều kiện kết thúc (count > 1), nên trong hàm countDown(1)
không gọi countDown(0)
, vì vậy "pop 1" được in ra và kết thúc hàm countDown(1)
. Lúc này, hàm countDown(1)
bật ra khỏi ngăn xếp, hàm countDown(2)
tiếp tục thực thi tại vị trí sau lời gọi hàm countDown(1)
, do đó "pop 2" được in ra. Tuần tự đến khi thoát ra toàn bộ các lời gọi hàm đệ quy.
Một số bài toán đệ quy kinh điển
Bài toán tính giai thừa
Cho n
là một số tự nhiên (n >= 0). Hãy tính giai thừa của n
(n!). Biết rằng 0! = 1 và n! = (n-1)! * n.
Phân tích:
- Để tính
n!
, ta cần phải tính(n-1)!
- Để tính
(n-1)!
, ta phải tính(n-2)!
- Và tiếp tục như vậy cho tới khi gặp trường hợp
0!
. Khi đó ta lập tức có kết quả là1
, không cần phải tính thông qua một kết quả trung gian khác.
long GiaiThua(int n) {
if (n == 0) {
return 1; // điều kiện dừng
}
return n * GiaiThua(n - 1); // gọi đệ quy
}
Dãy Fibonaci
Dãy Fibonaci là dãy vô hạn các số tự nhiên. Số Fibonaci thứ n
, ký hiệu F(n)
, được định nghĩa như sau:
F(n) = 0
, nếun = 0
F(n) = 1
, nếun = 1
F(n) = F(n-1) + F(n-2)
, nếun > 1
#include
using namespace std;
int fibonacci(int number) {
if (number == 0) return 0; // điều kiện dừng
if (number == 1) return 1; // điều kiện dừng
return fibonacci(number - 1) + fibonacci(number - 2);
}
int main() {
// in dãy 15 số fibonacci
for (int count = 0; count < 15; ++count)
cout << fibonacci(count) << " ";
return 0;
}
// Output:
// 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
Đệ quy so với vòng lặp
Một câu hỏi thường gặp là: "Tại sao lại sử dụng hàm đệ quy trong khi bạn có thể thực hiện với vòng lặp?".
Thông thường, các bài toán đệ quy có thể giải quyết bằng vòng lặp. Tuy nhiên, hàm đệ quy giúp code dễ đọc và đơn giản hơn.
Ví dụ: In dãy Fibonacci
#include
using namespace std;
int main() {
int n1 = 0, n2 = 1;
for (int i = 1; i <= 15; ++i) {
cout << n1 << " ";
int nextTerm = n1 + n2;
n1 = n2;
n2 = nextTerm;
}
return 0;
}
// Output:
// 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
Sử dụng vòng lặp thường có hiệu suất cao hơn so với phiên bản hàm đệ quy. Vì khi một hàm được gọi, chương trình sẽ tốn một lượng chi phí cho việc đưa hàm vào ngăn xếp (stack).
Chú ý: Ưu tiên sử dụng vòng lặp thay vì đệ quy.
Kết luận
Qua bài viết này, bạn đã nắm được khái niệm Đệ quy trong C++ (Recursion) và những bài toán cơ bản về đệ quy.
Trong bài tiếp theo, mình sẽ giới thiệu cho các bạn về Khuôn mẫu hàm trong C++ (Function templates).
Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên "Luyện tập - Thử thách - Không ngại khó".
Thảo luận
Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần Bình luận bên dưới hoặc trong mục Hỏi & Đáp trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.