Рекурсивная функция вызова в JavaScript

Я знаю, что вы должны слегка проступать при выполнении рекурсивных вызовов функций в JavaScript, потому что ваш второй вызов может быть в 10 раз медленнее.

Красноречивый JavaScript:

Есть одна важная проблема: во многих реализациях JavaScript эта вторая версия примерно в 10 раз медленнее первой. В JavaScript запуск простого цикла намного дешевле, чем вызов функции несколько раз.

Джон Ресиг даже говорит, что это проблема в этой публикации.

Мой вопрос: почему так неэффективно использовать рекурсию? Это просто способ создания конкретного двигателя? Мы когда-нибудь увидим время в JavaScript, где это не так?

Ответ 1

Вызов функций намного дороже, чем простой цикл из-за всех накладных расходов на изменение стека и создание нового контекста и т.д. Для того, чтобы рекурсия была очень эффективной, язык должен поддерживать некоторую форму устранения хвостового вызова, что в основном означает преобразование определенных видов рекурсивных функций в циклы. Функциональные языки, такие как OCaml, Haskell и Scheme, делают это, но никакая реализация JavaScript, о которой я знаю, не делает этого (это было бы незначительно полезно, если бы они не все сделали, поэтому, возможно, у нас есть проблема с обеденными философами).

Ответ 2

Это просто способ, которым построены конкретные JS-движки, используемые браузерами. Без устранения хвостового вызова вам нужно создавать новый стек кадров каждый раз, когда вы рекурсируете, тогда как с циклом он просто устанавливает счетчик программ обратно к началу его. Например, схема имеет это как часть спецификации языка, поэтому вы можете использовать рекурсию таким образом, не беспокоясь о производительности.

https://bugzilla.mozilla.org/show_bug.cgi?id=445363 указывает на прогресс, достигнутый в Firefox (и Брендан Эйх говорит здесь о том, что он, возможно, входит в спецификацию ECMAScript), но я не думаю, что какой-либо из существующих браузеров еще не реализовал.