Họ đang đo gì
Bạn có nghĩ tới giới hạn ngăn xếp không, và có biết JavaScript không có tối ưu đệ quy đuôi.
Trả lời ngắn~30 giây
Đệ quy đọc dễ hơn hẳn khi cấu trúc dữ liệu là cây hoặc đồ thị — duyệt cây, backtracking, chia để trị. Vòng lặp tốt hơn khi độ sâu có thể lớn, vì mỗi lời gọi tốn một khung trên ngăn xếp và ngăn xếp thì có giới hạn cứng. Trong Java mặc định khoảng vài nghìn khung; đệ quy trên một danh sách liên kết 100.000 phần tử sẽ tràn ngăn xếp trong khi vòng lặp thì không.
Giải thích sâu
Điều đáng biết là tối ưu đệ quy đuôi — biến lời gọi đệ quy cuối cùng thành một bước nhảy để không tốn khung mới — KHÔNG có ở nhiều môi trường phổ biến. JVM không làm; V8 có trong đặc tả ES6 nhưng không cài đặt. Nghĩa là “viết đệ quy đuôi cho an toàn” là lời khuyên đúng với Scala hoặc Kotlin và sai với Java hay JavaScript.
Khi cần cả tính dễ đọc của đệ quy lẫn an toàn của vòng lặp, cách chuẩn là tự quản lý ngăn xếp tường minh: dùng một Deque làm stack thay vì ngăn xếp lời gọi. Nó dài dòng hơn một chút và cho bạn kiểm soát hoàn toàn độ sâu, và với duyệt đồ thị lớn thì đó gần như luôn là lựa chọn đúng.
Câu hỏi tiếp theo họ sẽ hỏi
?Đệ quy có thể chậm hơn nhiều không?
Có, khi nó tính lại cùng một thứ nhiều lần — fib(n) đệ quy thuần là O(2ⁿ). Thêm ghi nhớ đưa nó về O(n), và cùng cách đó chính là bước chuyển từ đệ quy sang quy hoạch động.
Trả lời thế này là mất điểm
- Dùng đệ quy trên dữ liệu do người dùng cung cấp mà không giới hạn độ sâu. Đó là một lỗ hổng từ chối dịch vụ.