Рекурсивная функция вызова в 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), но я не думаю, что какой-либо из существующих браузеров еще не реализовал.
