Недавно я прочитал несколько статей (например, http://dailyjs.com/2012/09/14/functional-programming/ ) о функциональных аспектах Javascript и взаимосвязи между Scheme и Javascript (на последнюю повлияла первая, которая является функциональным языком, в то время как аспекты ОО унаследованы от Self, который является языком на основе прототипов).
Однако мой вопрос более конкретен: мне было интересно, есть ли показатели производительности рекурсии и итерации в Javascript.
Я знаю, что в некоторых языках (где по конструкции итерация работает лучше) разница минимальна, потому что интерпретатор / компилятор преобразует рекурсию в итерацию, однако я предполагаю, что, вероятно, это не тот случай с Javascript, поскольку он, по крайней мере частично, является функциональным язык.
Ответы:
JavaScript не выполняет оптимизацию хвостовой рекурсии , поэтому, если ваша рекурсия слишком глубока, вы можете получить переполнение стека вызовов. У итерации таких проблем нет. Если вы думаете, что собираетесь использовать слишком много рекурсии, и вам действительно нужна рекурсия (например, для выполнения заливки), замените рекурсию собственным стеком.
Производительность рекурсии, вероятно, хуже, чем производительность итераций, потому что вызовы и возвраты функций требуют сохранения и восстановления состояния, в то время как итерация просто переходит в другую точку функции.
источник
var stack = []; var factorial = function(n) { if(n === 0) { return 1 } else { stack[n-1] = n * factorial(n - 1); return stack[n-1]; } }elseв этой функции на,else if (stack[n-1]) { return stack[n-1]; } elseи у вас есть памятка . Кто бы ни написал этот факторный код, его реализация была неполной (и, вероятно, следовало бы использоватьstack[n]везде, а неstack[n-1]).Обновление : начиная с ES2015, JavaScript имеет TCO , поэтому часть приведенного ниже аргумента больше не действует.
Хотя в Javascript нет оптимизации хвостовых вызовов, рекурсия часто является лучшим способом. И искренне, за исключением крайних случаев, вы не получите переполнения стека вызовов.
Производительность - это то, что нужно учитывать, но преждевременная оптимизация тоже. Если вы думаете, что рекурсия более элегантна, чем итерация, то сделайте это. Если окажется, что это ваше узкое место (которое может никогда не быть), то вы можете заменить его на некрасивую итерацию. Но в большинстве случаев узким местом является манипулирование DOM или, в более общем смысле, ввод-вывод, а не сам код.
Рекурсия всегда более элегантна 1 .
1 : Личное мнение.
источник
Мне было довольно любопытно, что это за производительность в javascript, поэтому я провел несколько экспериментов (хотя и на более старой версии узла). Я написал рекурсивный факторный калькулятор против итераций и запускал его несколько раз локально. Результат казался довольно сильно искаженным к рекурсии, имеющей налог (ожидаемый).
Код: https://github.com/j03m/trickyQuestions/blob/master/factorial.js
источник
"use strict";и посмотреть, если это имеет значение. (Он выдастjumps вместо стандартной последовательности вызовов)В соответствии с запросом ОП я скину (не дурачу себя, надеюсь: P)
Я думаю, что мы все согласны с тем, что рекурсия - это просто более элегантный способ кодирования. Если все сделано правильно, это может сделать код более легким для сопровождения, что, по-моему, так же важно (если не больше), как снижение затрат на 0,0001 мс.
Что касается аргумента, что JS не выполняет оптимизацию Tail-call: это уже не совсем верно, использование строгого режима ECMA5 позволяет TCO. Это было то, что я не был слишком счастлив некоторое время назад, но, по крайней мере, теперь я знаю, почему
arguments.calleeвыдает ошибки в строгом режиме. Я знаю, что ссылка выше ссылается на отчет об ошибке, но ошибка установлена на WONTFIX. Кроме того, ожидается стандартная TCO: ECMA6 (декабрь 2013 г.).Инстинктивно, придерживаясь функциональной природы JS, я бы сказал, что рекурсия - более эффективный стиль кодирования в 99,99% случаев. Тем не менее, у Флориана Маргэйна есть пункт, когда он говорит, что узкое место может быть найдено в другом месте. Если вы манипулируете DOM, вам, вероятно, лучше всего сосредоточиться на написании своего кода, насколько это возможно. DOM API - это то, что он есть: медленно.
Я думаю, что невозможно дать однозначный ответ, какой вариант является более быстрым. В последнее время многие jspref, которые я видел, показывают, что движок Chrome V8 смехотворно быстр в некоторых задачах, которые работают в 4 раза медленнее на Fider SpiderMonkey и наоборот. Современные движки JS имеют всевозможные хитрости для оптимизации вашего кода. Я не эксперт, но я чувствую, что V8, например, высоко оптимизирован для замыканий (и рекурсии), тогда как движок MS JScript - нет. SpiderMonkey часто работает лучше, когда DOM задействован ...
Вкратце: я бы сказал, какая техника будет более эффективной, как всегда в JS, почти невозможно предсказать.
источник
Без строгого режима производительность итерации обычно немного выше, чем рекурсия ( в дополнение к тому, что JIT выполняет больше работы ). Оптимизация хвостовой рекурсии, по существу, устраняет любые заметные различия, поскольку она превращает всю последовательность вызовов в скачок.
Пример: Jsperf
Я бы посоветовал гораздо больше беспокоиться о ясности и простоте кода, когда дело доходит до выбора между рекурсией и итерацией.
источник