Đệ quy (Recursion)

Đệ quy là kỹ thuật một hàm tự gọi lại chính nó để giải quyết một bài toán bằng cách chia nhỏ nó thành các bài toán con tương tự nhưng đơn giản hơn.

Ví dụ kinh điển: giai thừa

#include <iostream>

int factorial(int n) {
    if (n <= 1) {
        return 1; // Trường hợp dừng (base case) - BẮT BUỘC phải có
    }
    return n * factorial(n - 1); // Hàm tự gọi lại chính nó
}

int main() {
    std::cout << factorial(5) << std::endl; // 120 (5 * 4 * 3 * 2 * 1)
    return 0;
}

Mỗi hàm đệ quy cần có hai phần:

1. Trường hợp dừng (base case): điều kiện để hàm dừng gọi lại chính nó
2. Trường hợp đệ quy (recursive case): hàm gọi lại chính nó với dữ liệu đầu vào nhỏ hơn/đơn giản hơn

Thiếu trường hợp dừng sẽ khiến hàm gọi lại vô hạn, gây lỗi stack overflow khi chương trình hết bộ nhớ stack dành cho lời gọi hàm.

Hình dung cách đệ quy hoạt động

factorial(5)
= 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * 1)))
= 120

Mỗi lời gọi hàm được đặt lên call stack, và chỉ khi lời gọi trong cùng kết thúc, các lời gọi bên ngoài mới lần lượt tính ra kết quả cuối cùng.

Dãy Fibonacci bằng đệ quy

#include <iostream>

int fibonacci(int n) {
    if (n <= 1) {
        return n; // Trường hợp dừng: fib(0) = 0, fib(1) = 1
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    for (int i = 0; i < 10; i++) {
        std::cout << fibonacci(i) << " ";
    }
    // 0 1 1 2 3 5 8 13 21 34

    return 0;
}

Đệ quy trên cấu trúc dữ liệu: duyệt mảng

#include <iostream>
#include <vector>

int sum_recursive(const std::vector<int>& numbers, size_t index) {
    if (index >= numbers.size()) {
        return 0; // Trường hợp dừng: đã duyệt hết mảng
    }
    return numbers[index] + sum_recursive(numbers, index + 1);
}

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    std::cout << sum_recursive(numbers, 0) << std::endl; // 15

    return 0;
}

Vấn đề hiệu năng: đệ quy có thể rất chậm

Fibonacci đệ quy ở trên có một vấn đề nghiêm trọng: nó tính lại cùng một giá trị nhiều lần. fibonacci(5) gọi fibonacci(4) và fibonacci(3), nhưng fibonacci(4) lại gọi fibonacci(3) một lần nữa - dẫn đến số lượng lời gọi tăng theo cấp số mũ. Kỹ thuật memoization (đã gặp ở dạng decorator trong nhiều ngôn ngữ khác) giải quyết vấn đề này bằng cách lưu lại kết quả đã tính:

#include <iostream>
#include <unordered_map>

std::unordered_map<int, long long> cache;

long long fibonacci_memo(int n) {
    if (n <= 1) return n;
    if (cache.find(n) != cache.end()) {
        return cache[n]; // Đã tính trước đó, dùng lại kết quả
    }
    long long result = fibonacci_memo(n - 1) + fibonacci_memo(n - 2);
    cache[n] = result; // Lưu lại để dùng cho lần sau
    return result;
}

int main() {
    std::cout << fibonacci_memo(40) << std::endl; // Nhanh hơn rất nhiều so với bản không cache
    return 0;
}

Khi nào dùng đệ quy, khi nào dùng vòng lặp?

Bất kỳ bài toán đệ quy nào cũng có thể viết lại bằng vòng lặp (và ngược lại), nhưng:

• Đệ quy thường phù hợp và dễ đọc hơn với bài toán có cấu trúc “chia để trị” tự nhiên (cây, đồ thị, thuật toán chia đôi…)
• Vòng lặp thường hiệu quả hơn về hiệu năng (không tốn thêm bộ nhớ cho call stack) và nên ưu tiên cho các bài toán đơn giản, tuyến tính

Tổng kết

• Hàm đệ quy tự gọi lại chính nó, luôn cần có trường hợp dừng (base case) để tránh gọi vô hạn
• Thiếu trường hợp dừng sẽ gây lỗi stack overflow
• Đệ quy “ngây thơ” có thể tính lại cùng giá trị nhiều lần - dùng memoization để lưu kết quả và tăng tốc
• Chọn đệ quy khi bài toán có cấu trúc chia để trị tự nhiên; chọn vòng lặp khi cần hiệu năng tối ưu cho bài toán đơn giản