Trong lập trình, có một kỹ thuật nghe có vẻ “khó hiểu” nhưng lại rất mạnh mẽ: đệ quy. Thực chất, đệ quy chỉ đơn giản là khi một hàm tự gọi lại chính mình để giải quyết bài toán bằng cách chia nhỏ nó ra. Vậy đệ quy là gì và vì sao nó lại quan trọng trong thuật toán? Hãy cùng Code Dream tìm hiểu theo cách đơn giản nhất trong bài viết sau nhé.
Khái niệm về thuật toán đệ quy
Đệ quy là một kỹ thuật trong lập trình khi một hàm tự gọi lại chính nó để giải quyết bài toán.
Thay vì xử lý toàn bộ vấn đề cùng lúc, đệ quy sẽ chia bài toán lớn thành những bài toán nhỏ hơn có cùng dạng, rồi giải dần cho đến khi gặp điều kiện dừng (trường hợp đơn giản nhất để kết thúc).
Hiểu đơn giản: Đệ quy là cách “giải việc lớn bằng cách lặp lại cách giải việc nhỏ hơn giống nó”
Một thuật toán đệ quy luôn có hai thành phần quan trọng:
- Điều kiện dừng (base case): Trường hợp đơn giản nhất để kết thúc việc gọi lại.
- Bước đệ quy (recursive case): Phần tiếp tục chia nhỏ bài toán và gọi lại chính thuật toán đó.
Một số ứng dụng cơ bản của Đệ quy
Đệ quy là kỹ thuật cho phép một hàm tự gọi lại chính nó để giải quyết bài toán bằng cách chia nhỏ thành các bài toán con đơn giản hơn. Nhờ đó, code thường ngắn gọn và dễ hiểu hơn trong nhiều trường hợp.
Thuật toán tìm kiếm và sắp xếp:
Đệ quy được dùng trong các thuật toán như tìm kiếm nhị phân, Merge Sort, Quick Sort. Ví dụ tìm kiếm nhị phân:
int binarySearch(int a[], int left, int right, int x) {
if(left > right) return -1;
int mid = (left + right) / 2;
if(a[mid] == x) return mid;
else if(a[mid] > x)
return binarySearch(a, left, mid - 1, x);
else
return binarySearch(a, mid + 1, right, x);
}
Xử lý cây (tree) và đồ thị (graph):
Đệ quy giúp duyệt các cấu trúc phân cấp như cây hoặc đồ thị, ví dụ duyệt cây nhị phân:
struct Node {
int val;
Node* left;
Node* right;
};
void inorder(Node* root) {
if(root == NULL) return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
Quy hoạch động:
Đệ quy là nền tảng để giải các bài toán tối ưu như Fibonacci:
int fib(int n) {
if(n <= 1) return n;
return fib(n-1) + fib(n-2);
}
Những bài tập áp dụng đệ quy thường gặp trong C++
Đệ quy là kỹ thuật quan trọng trong lập trình, đặc biệt phù hợp với các bài toán có thể chia nhỏ thành các bài toán con giống nhau. Khi sử dụng đệ quy, mỗi bài toán cần xác định rõ điều kiện dừng (base case) và công thức gọi lại (recursive case).
Dưới đây là các dạng bài phổ biến:
Tính giai thừa (Factorial)
Bài toán
Tính n!=n×(n−1)×...×1n! = n \times (n-1) \times ... \times 1n!=n×(n−1)×...×1
int factorial(int n) {
if(n == 0) return 1;
return n * factorial(n - 1);
}
- Phân tích
Base case: n = 0 hoặc 1 → trả về 1
Đệ quy: gọi lại chính nó với n – 1
Độ phức tạp: O(n)
Dãy Fibonacci
Bài toán
F(n) = F(n-1) + F(n-2)
int fib(int n) {
if(n <= 1) return n;
return fib(n-1) + fib(n-2);
}
Phân tích
Gọi lặp lại nhiều lần → không tối ưu
Độ phức tạp: O(2^n)
Thường cải tiến bằng quy hoạch động
Tính tổng các phần tử mảng
int sum(int n) {
if(n == 1) return 1;
return n + sum(n-1);
}
- Phân tích
Mỗi lần giảm kích thước mảng đi 1
Độ phức tạp: O(n)
Tháp Hà Nội (Tower of Hanoi)
void hanoi(int n, char A, char B, char C) {
if(n == 1) {
cout << A << " -> " << C << endl;
return;
}
hanoi(n-1, A, C, B);
cout << A << " -> " << C << endl;
hanoi(n-1, B, A, C);
}
- Phân tích
Chia bài toán thành 3 bước
Độ phức tạp: O(2^n)
Tìm kiếm nhị phân (Binary Search)
int binarySearch(int a[], int left, int right, int x) {
if(left > right) return -1;
int mid = (left + right) / 2;
if(a[mid] == x) return mid;
if(a[mid] > x) return binarySearch(a, left, mid-1, x);
return binarySearch(a, mid+1, right, x);
}
- Phân tích
Chia đôi mảng mỗi lần
Độ phức tạp: O(log n)
Tóm lại, đệ quy không chỉ là một kỹ thuật lập trình, mà còn là một cách tư duy quan trọng trong giải thuật: biết cách chia nhỏ vấn đề và xử lý từng phần một cách logic. Khi nắm vững bản chất của đệ quy điều kiện dừng rõ ràng và bước chia hợp lý bạn sẽ có thêm một công cụ mạnh mẽ để chinh phục nhiều bài toán từ cơ bản đến nâng cao.
Nếu bạn muốn được học bài bản về tư duy thuật toán, rèn luyện kỹ năng giải bài cho các kỳ thi Tin học trẻ, HSG TP/quốc gia hay ôn thi vào các trường chuyên và đại học top công nghệ, Code Dream là môi trường phù hợp để bạn phát triển.
Tại Code Dream, học sinh được đào tạo chuyên sâu về lập trình thi đấu với giáo trình độc quyền, lộ trình rõ ràng theo từng cấp độ và đội ngũ giáo viên giàu kinh nghiệm đến từ các trường chuyên như Nguyễn Huệ, Hà Nội – Amsterdam, Chu Văn An.
Tư duy thuật toán vững chắc hôm nay chính là nền tảng cho thành tích và cơ hội lớn trong tương lai. Hãy liên hệ với chúng tôi ngay hôm nay nhé.
