Làm thế nào để xử lý hiện tượng tràn bộ nhớ Stack Overflow khi tính toán số Fibonacci với giá trị N lớn bằng phương pháp đệ quy thuần túy và cách khắc phục?

Question

Accepted Answer

Bản chất vấn đề
Khi sử dụng phương pháp đệ quy thuần túy để tính số Fibonacci, mỗi lời gọi hàm sẽ tạo ra một Stack Frame mới trên Call Stack để lưu trữ các biến cục bộ và địa chỉ trả về. Khi N có giá trị lớn (ví dụ N > 1000), số lượng lời gọi hàm lồng nhau vượt quá giới hạn của Call Stack, dẫn đến ngoại lệ Stack Overflow.
Giải pháp khắc phục
Để khắc phục, kỹ sư có thể chuyển đổi thuật toán từ đệ quy sang vòng lặp Iteration (Bottom-up) để giữ độ phức tạp không gian ở mức O(1), hoặc sử dụng kỹ thuật Tail Recursion nếu ngôn ngữ hỗ trợ TCO (Tail Call Optimization).
Ví dụ minh họa bằng JavaScript
function fibonacciIterative(n) {
    if (n <= 1) return n;
    let prev2 = 0;
    let prev1 = 1;
    let current = 0;
    for (let i = 2; i <= n; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return current;
}
Lưu ý thực chiến
Ở cấp độ Junior, việc hiểu rõ giới hạn phần cứng của Call Stack giúp tránh các lỗi nghiêm trọng trên môi trường Production khi hệ thống phải xử lý lượng dữ liệu lớn hoặc các thuật toán chưa được tối ưu.

Làm thế nào để xử lý hiện tượng tràn bộ nhớ Stack Overflow khi tính toán số Fibonacci với giá trị N lớn bằng phương pháp đệ quy thuần túy và cách khắc phục?

Bản chất vấn đề

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi fibonacci series liên quan cùng chủ đề