Giới thiệu về đệ quy

Đệ quy là một kỹ thuật lập trình trong đó một hàm gọi chính nó để giải quyết vấn đề. Thay vì dùng vòng lặp, các hàm đệ quy chia vấn đề phức tạp thành những vấn đề con nhỏ hơn, tương tự nhau, cho đến khi gặp một trường hợp đơn giản có thể giải quyết trực tiếp.

Mọi hàm đệ quy đều phải có hai thành phần thiết yếu. Trường hợp cơ sở là điều kiện dừng đệ quy. Nếu thiếu điều kiện này, hàm sẽ gọi chính nó mãi mãi. Bước đệ quy là phần hàm gọi lại chính nó với các tham số đã thay đổi, mỗi lần gọi lại tiến gần hơn đến trường hợp cơ sở.

Đây là một ví dụ đếm ngược đơn giản minh họa đệ quy:

void countdown(int n) {
    if (n <= 0) {           // Trường hợp cơ sở: dừng khi n bằng 0
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // Bước đệ quy: gọi với n-1
}

Khi gọi countdown(3), hàm in ra 3, sau đó gọi countdown(2), hàm này in ra 2, rồi gọi countdown(1), cứ thế cho đến khi chạm đến trường hợp cơ sở. Mỗi lần gọi hàm chờ lần gọi tiếp theo hoàn tất rồi mới kết thúc, tạo thành một chuỗi các lần gọi cuối cùng sẽ lần lượt quay lại hàm gọi ban đầu.