Я знаю, что вы можете переписать рекурсивную функцию, используя простой цикл, используя массив в качестве очереди "первым в первом" "оставшейся работы". Я слышал, что это делает менее вероятным переполнение стека.
Но если переполнение стека не является проблемой (потому что вы не очень сильно рекурсивно), есть ли причины предпочесть итеративный рекурсивный? Это быстрее?
Меня больше всего интересует JavaScript на V8.
В Javascript, который не (не требуется и, возможно, не может видеть комментарии), делает оптимизацию хвостовой рекурсии, рекурсия медленнее, чем итерация (потому что почти на каждом языке вызов функции намного дороже, чем скачок) и имеет возможность вызвать ошибки, если вы слишком сильно усложняете (однако, предел может быть довольно глубоким, Chrome ушел с глубиной рекурсии 16 316 в моем эксперименте).
Однако влияние производительности иногда стоит ясности кода, который вы получаете при написании рекурсивной функции, а некоторые вещи намного сложнее сделать без рекурсии (рекурсивные функции почти всегда намного короче, чем их итеративные копии), например работая с деревьями (но вы на самом деле не так много делаете с Javascript. Edit: GGG упомянул, что DOM - это дерево, и работа с ним очень распространена в JS).
Рекурсия может завершиться быстрее, поскольку бесконечно рекурсивная функция выдует стек, создавая исключение, из которого программа может восстановить, в то время как итерационное решение будет выполняться до тех пор, пока не остановится внешним агентом.
Для кода, который будет выдавать допустимый выходной заданный момент времени, основная стоимость рекурсии - служебные вызовы функций. Итеративные решения просто не имеют этого, поэтому имеют тенденцию выигрывать в критическом критически важном коде на языках, которые явно не оптимизируются для рекурсии.
Это определенно заметно в тестах, но если вы не пишете критический код производительности, ваши пользователи, вероятно, не заметят.
Тесты на http://jsperf.com/function-call-overhead-test пытаются количественно определить накладные расходы функций в различных интерпретаторах JS. Я бы собрал аналогичный тест, который явно проверяет рекурсию, если вы беспокоитесь.
Обратите внимание, что оптимизация рекурсии хвостового вызова трудно сделать правильно в EcmaScript 3.
Например, простая реализация сгибания массива в JavaScript:
function fold(f, x, i, arr) {
if (i === arr.length) { return x; }
var nextX = f(x, arr[i]);
return fold(f, nextX, i+1, arr);
}
не может быть оптимизирован по хвосту, потому что вызов
fold(eval, 'var fold=alert', 0, [0])
был бы eval('var fold=alert') внутри тела fold, заставив, казалось бы, хвосторекурсивный вызов fold не быть фактически рекурсивным.
EcmaScript 5 изменил eval, чтобы не быть вызываемым, за исключением имени eval, а строгий режим запрещает eval вводить локальные переменные, но оптимизация хвостового вызова зависит от способности статически определять, где хвост-вызов идет, что не всегда возможно в динамических языках, таких как JavaScript.
Это зависит... Я задавал один и тот же вопрос, когда у меня возникала ошибка "Slow script" в IE8 в рекурсивной функции. И был удивлен, что итерация была на самом деле еще медленнее.
Я шел по дереву, ища конкретный node. И я переписал свою рекурсивную функцию итеративным способом (используя стек для сохранения контекста) с использованием аналогичного подхода: fooobar.com/info/26497/...
После этого я, однако, начал получать гораздо больше "Slow script" из IE 8, чем раньше. Выполнение некоторого профилирования подтвердило, что итеративная версия была еще медленнее.
Причиной этого может быть то, что использование стека вызовов методов в JS, вероятно, быстрее, чем использование массива с соответствующими операциями push() и pop() в цикле. Чтобы проверить это, я создал тест, который имитирует движение дерева в обоих случаях: http://jsperf.com/recursion-vs-iteration-852 Результаты удивляют. Хотя в Chrome итеративная версия (в моем случае) на 19% медленнее, в IE8 итеративная версия на 65% медленнее, чем рекурсивная версия.