Gọi hàm đệ quy trong JavaScript

Question

Tôi biết bạn nên lướt nhẹ khi thực hiện các cuộc gọi đệ quy đến các hàm trong JavaScript vì cuộc gọi thứ hai của bạn có thể chậm hơn tới 10 lần.

Eloquent JavaScript trạng thái:

Có một vấn đề quan trọng: Trong hầu hết các trường JavaScript, phiên bản thứ hai này là khoảng 10 lần chậm hơn lần thứ nhất. Trong JavaScript, chạy một vòng lặp đơn giản rẻ hơn rất nhiều so với việc gọi một hàm nhiều lần.

John Resig thậm chí còn cho biết đây là sự cố trong this bài đăng.

Câu hỏi của tôi là: Tại sao việc sử dụng đệ quy lại không hiệu quả? Nó chỉ là cách một động cơ cụ thể được xây dựng? Liệu chúng ta có bao giờ nhìn thấy một thời gian trong JavaScript mà đây không phải là trường hợp?

Answer 1

Cuộc gọi chức năng chỉ đắt hơn một vòng lặp đơn giản do tất cả chi phí thay đổi ngăn xếp và thiết lập ngữ cảnh mới, v.v. Để đệ quy trở nên rất hiệu quả, một ngôn ngữ phải hỗ trợ một số dạng cắt bỏ cuộc gọi đuôi, về cơ bản có nghĩa là chuyển đổi một số loại hàm đệ quy nhất định thành các vòng lặp. Các ngôn ngữ chức năng như OCaml, Haskell và Scheme thực hiện điều này, nhưng không thực hiện JavaScript mà tôi nhận thức được (nó sẽ chỉ hữu ích một cách hữu ích trừ khi tất cả chúng đều có, vì vậy có lẽ chúng ta có vấn đề về triết lý ăn uống).

Answer 2

Đây chỉ là cách mà các công cụ JS cụ thể mà trình duyệt sử dụng được xây dựng, có. Nếu không có cuộc gọi loại bỏ đuôi, bạn phải tạo một khung ngăn xếp mới mỗi khi bạn recurse, trong khi với một vòng lặp nó chỉ cần thiết lập các chương trình truy cập trở lại để bắt đầu của nó. Đề án, ví dụ, có điều này như là một phần của đặc tả ngôn ngữ, vì vậy bạn có thể sử dụng đệ quy theo cách này mà không đáng lo ngại về hiệu suất.

https://bugzilla.mozilla.org/show_bug.cgi?id=445363 cho biết tiến trình đang được thực hiện trong Firefox (và Brendan Eich nói ở đây về nó có thể là một phần của thông số ECMAScript), nhưng tôi không nghĩ bất kỳ trình duyệt hiện tại nào đã được triển khai thực hiện.