Vấn đề lớn nhất với dòng mã là thời gian phức tạp của thuật toán, khi bạn sử dụng đệ quy đơn giản, bạn sẽ tính toán lại mọi thứ và thực hiện nhiều công việc gấp đôi. Điều này là do khi bạn tính toán fib (n) bằng cách sử dụng
int fib(int n) {
if (n < 2) { return 1; }
return fib(n-1) + fib(n-2)
}
bạn sẽ tính toán fib (n-1), tính toán fib (n-2) và fib (n-3). Nhưng để tính toán fib (n), bạn sẽ tính toán fib (n-2). Để cải thiện điều này, bạn sẽ cần phải lưu trữ các kết quả tạm thời. Điều này thường dễ dàng hơn khi sử dụng lặp lại và bắt đầu từ i = 0 lên đến n. Bằng cách này bạn có thể dễ dàng lưu trữ hai kết quả cuối cùng và tránh tính toán cùng một giá trị hơn và hơn.
Cách dễ dàng để xem thuật toán có hiệu quả hay không là thử và giải quyết nó cho một vài ví dụ ngày càng khó hơn. Bạn cũng có thể tính toán chính xác hơn. Lấy ví dụ về mã vạch ở trên. Gọi fib (n) sẽ có sự phức tạp O(fib(n)) = O(fib(n-1)) +O(fib(n-2)) + 1 (chúng ta hãy lấy 1 để bổ sung).Giả sử rằng O(fib(0)) = O(fib(1)) = 1. Điều này có nghĩa là O(fib(2)) = 3, O(fib((3)) = 5, O(fib(4)) = 9. Như bạn có thể thấy, loạt bài này sẽ đi nhanh hơn so với dòng mã nguồn gốc chính nó! Điều này có nghĩa là một lượng lớn sự phức tạp ngày càng tăng. Khi bạn sẽ có một thuật toán lặp với vòng lặp for từ 0 đến n, độ phức tạp của bạn sẽ tăng theo thứ tự của n, điều này sẽ tốt hơn.
Để biết thêm thông tin, hãy kiểm tra ký hiệu lớn-o.
Nếu bạn sử dụng ints hoặc longs bạn sẽ không đi xa hơn 60 hoặc 70 lần thu thập để nó không thực sự quan trọng. Và bạn cũng có thể lưu trữ kết quả bằng phương pháp đệ quy. – assylias
Ngoài ra: [đệ quy-hoặc-looping?] (Http://stackoverflow.com/questions/13346424/recursion-or-looping?lq=1) – nawfal