Đệ quy trong C++
Hiểu cách một hàm tự gọi chính nó, điều kiện dừng, call stack và quá trình trả kết quả.
Mục tiêu học tập
- Hiểu đệ quy là gì và khi nào nên dùng.
- Biết vai trò của điều kiện dừng trong hàm đệ quy.
- Theo dõi được call stack khi hàm gọi chính nó.
- Viết được hàm factorial bằng C++ và phân tích độ phức tạp.
Kiến thức cần có
- Biết khai báo hàm trong C++.
- Biết câu lệnh điều kiện if.
- Biết phép nhân và kiểu số nguyên cơ bản.
Video bài học
Lý thuyết
Đệ quy là kỹ thuật trong đó một hàm gọi lại chính nó để giải một bài toán nhỏ hơn. Một hàm đệ quy thường có hai phần quan trọng: điều kiện dừng và bước gọi đệ quy.
- Điều kiện dừng: trường hợp nhỏ nhất có thể trả kết quả ngay.
- Bước đệ quy: gọi lại hàm với dữ liệu nhỏ hơn, gần điều kiện dừng hơn.
Ví dụ với giai thừa: factorial(4) được tính thành 4 * factorial(3), rồi tiếp tục cho tới factorial(1).
Trực quan hóa
Mô phỏng call stack factorial(4)
Gọi factorial(4). Vì n chưa bằng 1 nên hàm tiếp tục gọi factorial(3).
Đệ quy luôn cần điều kiện dừng và bước gọi lại trên bài toán nhỏ hơn.
if (n <= 1) return 1;return n * factorial(n - 1);// kết quả được trả ngược từ lời gọi nhỏ nhất
Ví dụ code
#include <iostream>
using namespace std;
int factorial(int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
int main() {
cout << factorial(4);
return 0;
}
Kết quả chương trình
24
Độ phức tạp
Hàm gọi từ n xuống 1, nên thời gian là O(n). Vì mỗi lời gọi chưa trả về nằm trên call stack, bộ nhớ cũng là O(n).
Lỗi thường gặp
- Quên điều kiện dừng, khiến hàm gọi mãi và gây tràn stack.
- Gọi đệ quy nhưng không làm bài toán nhỏ hơn, ví dụ gọi lại
factorial(n). - Nhầm thứ tự trả kết quả: lời gọi nhỏ nhất trả về trước, sau đó các lời gọi lớn hơn mới tiếp tục tính.
Quiz
Kiểm tra hiểu bài Đệ quy
Luyện tập
- Viết hàm đệ quy tính tổng từ 1 đến n.
- Viết hàm đệ quy tính Fibonacci cơ bản với n nhỏ.
- Sửa factorial để in ra n ở mỗi lần gọi hàm, rồi quan sát thứ tự chạy.
Tóm tắt
Đệ quy giúp chia bài toán thành các bài toán nhỏ hơn. Muốn đệ quy chạy đúng, hãy luôn xác định điều kiện dừng và đảm bảo mỗi lần gọi tiến gần hơn tới điều kiện đó.