Почему циклы быстрее, чем рекурсия?

На практике я понимаю, что любая рекурсия может быть записана как цикл (и наоборот (?)), И если мы проводим измерения на реальных компьютерах, мы обнаруживаем, что циклы быстрее, чем рекурсия для той же проблемы. Но есть ли какая-либо теория, которая делает это различие, или это в основном эмпирический?

Причина, по которой циклы быстрее рекурсии, проста.
Петля выглядит так в сборке.

mov loopcounter,i
dowork:/do work
dec loopcounter
jmp_if_not_zero dowork

Один условный переход и некоторая бухгалтерия для счетчика цикла.

Рекурсия (когда она не оптимизирована или не может быть оптимизирована) выглядит следующим образом:

start_subroutine:
pop parameter1
pop parameter2
dowork://dowork
test something
jmp_if_true done
push parameter1
push parameter2
call start_subroutine
done:ret

Это намного сложнее, и вы получаете по крайней мере 3 прыжка (1 тест, чтобы увидеть, были ли выполнены, один вызов и один возврат).
Также в рекурсии параметры должны быть установлены и извлечены.
Ничего из этого не требуется в цикле, потому что все параметры уже настроены.

Теоретически параметры могут оставаться на месте и при рекурсии, но никакие компиляторы, о которых я знаю, на самом деле не заходят так далеко в своей оптимизации.

Различия между вызовом и jmp.
Пара «звонок-возврат» не намного дороже, чем jmp. Пара занимает 2 цикла, а jmp - 1; едва заметно.
В соглашениях о вызовах, которые поддерживают параметры регистра, накладные расходы для параметров минимальны, но даже параметры стека дешевы, если буферы ЦП не переполняются .
Это накладные расходы на установку вызова, продиктованные соглашением о вызовах и используемой обработкой параметров, которые замедляют рекурсию.
Это очень сильно зависит от реализации.

Пример плохой обработки рекурсии Например, если передан параметр, который подсчитан по ссылке (например, неконстантный параметр управляемого типа), он добавит 100 циклов, выполняя заблокированную настройку подсчета ссылок, полностью убивая производительность по сравнению с циклом.
На языках, настроенных на рекурсию, такого плохого поведения не происходит.

Оптимизация ЦП
Другая причина, по которой рекурсия медленнее, заключается в том, что она работает против механизмов оптимизации в ЦП.
Возвращения могут быть предсказаны правильно, только если их не слишком много в ряду. ЦП имеет буфер стека возврата с (несколькими) горстками записей. Как только они закончатся, каждый дополнительный возврат будет неверно предсказан, что приведет к огромным задержкам.
На любом процессоре, который использует рекурсию на основе буфера возврата стека, которая превышает размер буфера, лучше избегать.

О тривиальных примерах кода с использованием рекурсии
Если вы используете тривиальный пример рекурсии, такой как генерация чисел Фибоначчи, то эти эффекты не возникают, потому что любой компилятор, который «знает» о рекурсии, преобразует его в цикл, как любой программист, достойный его внимания было бы.
Если вы запустите эти тривиальные примеры в среде, которая не оптимизируется должным образом, то стек вызовов (излишне) вырастет за пределы.

О хвостовой рекурсии
Обратите внимание, что иногда компилятор оптимизирует удаленную хвостовую рекурсию, превращая ее в цикл. Лучше всего полагаться на это поведение только в тех языках, которые имеют хорошую репутацию в этом отношении.
Многие языки вставляют скрытый код очистки перед окончательным возвратом, предотвращая оптимизацию хвостовой рекурсии.

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

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

Неправильное использование рекурсии
Нет необходимости вычислять последовательность Фибоначчи с использованием рекурсии, фактически это патологический пример.
Рекурсию лучше всего использовать в языках, которые ее явно поддерживают, или в областях, где рекурсия сияет, например при обработке данных, хранящихся в дереве.

Я понимаю, что любая рекурсия может быть записана как цикл

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

Эти другие ответы несколько вводят в заблуждение. Я согласен, что они заявляют детали реализации, которые могут объяснить это несоответствие, но они преувеличивают случай. Как правильно предложено jmite, они ориентированы на реализацию для неработающих реализаций вызовов функций / рекурсии. Многие языки реализуют циклы с помощью рекурсии, поэтому циклы явно не будут быстрее в этих языках. Рекурсия ни в коем случае не менее эффективна, чем зацикливание (если применимо оба) в теории. Позвольте мне процитировать тезис к статье Гая Стила 1977 года « Разоблачение мифа о« дорогостоящем вызове процедуры »или, реализация процедур, считающихся вредными, или, Лямбда: окончательный вариант GOTO

Фольклор утверждает, что операторы GOTO «дешевы», а вызовы процедур «дороги». Этот миф в значительной степени является результатом плохо разработанных языковых реализаций. Исторический рост этого мифа считается. Обсуждаются как теоретические идеи, так и существующая реализация, которые развенчивают этот миф. Показано, что неограниченное использование процедурных вызовов обеспечивает большую стилистическую свободу. В частности, любая блок-схема может быть написана как «структурированная» программа без введения дополнительных переменных. Сложность с оператором GOTO и вызовом процедуры характеризуется как конфликт между абстрактными концепциями программирования и конкретными языковыми конструкциями.

«Конфликт между абстрактными концепциями программирования и конкретными языковыми конструкциями» можно увидеть из того факта, что большинство теоретических моделей, например, нетипизированного лямбда-исчисления , не имеют стека . Конечно, этот конфликт не является необходимым, как показано в вышеприведенном документе, и как это демонстрируют языки, у которых нет итерационного механизма, кроме рекурсии, такие как Haskell.

fixfix f x = f (fix f) x$(\lambda x.M)N \leadsto M[N/x]$$[N/x]$$x$$M$$N$$\leadsto$

Теперь для примера. Определить factкак

fact = fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1

Вот оценка fact 3, где, для компактности, я буду использовать в gкачестве синонима fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)), то есть fact = g 1. Это не влияет на мой аргумент.

fact 3 
~> g 1 3
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1 3 
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 1 3
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 1 3
~> (λn.if n == 0 then 1 else g (1*n) (n-1)) 3
~> if 3 == 0 then 1 else g (1*3) (3-1)
~> g (1*3) (3-1)
~> g 3 2
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 3 2
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 3 2
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 3 2
~> (λn.if n == 0 then 3 else g (3*n) (n-1)) 2
~> if 2 == 0 then 3 else g (3*2) (2-1)
~> g (3*2) (2-1)
~> g 6 1
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 1
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 1
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 1
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 1
~> if 1 == 0 then 6 else g (6*1) (1-1)
~> g (6*1) (1-1)
~> g 6 0
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 0
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 0
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 0
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 0
~> if 0 == 0 then 6 else g (6*0) (0-1)
~> 6

Вы можете увидеть из фигуры, даже не глядя на детали, что рост отсутствует, и каждой итерации требуется одинаковое количество места. (Технически, числовой результат растет, что неизбежно и так же верно для whileцикла.) Я не хочу, чтобы вы указывали на безгранично растущий «стек» здесь.

Кажется, что архетипическая семантика лямбда-исчисления уже выполняет то, что обычно называют «оптимизацией хвостового вызова». Конечно, никакой «оптимизации» здесь не происходит. Здесь нет особых правил для «хвостовых» вызовов, в отличие от «обычных» вызовов. По этой причине трудно дать «абстрактную» характеристику того, что делает хвостовой вызов «оптимизация», так как во многих абстрактных характеристиках семантики вызова функций нет ничего, что хвостовой вызов «оптимизации» мог бы сделать!

То, что аналогичное определение factво многих языках «переполнение стека», является неспособностью этих языков правильно реализовать семантику вызова функций. (У некоторых языков есть оправдание.) Ситуация примерно аналогична языковой реализации, в которой реализованы массивы со связанными списками. Индексирование в такие «массивы» будет тогда операцией O (n), которая не соответствует ожиданиям массивов. Если бы я сделал отдельную реализацию языка, которая использовала бы реальные массивы вместо связанных списков, вы бы не сказали, что я реализовал «оптимизацию доступа к массивам», вы бы сказали, что я исправил неправильную реализацию массивов.

Итак, отвечая на ответ Ведрака. Стеки не являются "фундаментальными" для рекурсии . В той степени, в которой «подобное стеку» поведение происходит в ходе оценки, это может происходить только в тех случаях, когда циклы (без вспомогательной структуры данных) не будут применимы в первую очередь! Иными словами, я могу реализовать циклы с рекурсией с точно такими же характеристиками производительности. Действительно, и Scheme, и SML содержат циклические конструкции, но обе они определяют их с точки зрения рекурсии (и, по крайней мере в Scheme, doчасто реализуются как макрос, который расширяется до рекурсивных вызовов.) Точно так же, для ответа Йохана ничего не говорит Компилятор должен выдать сборку, описанную Йоханом для рекурсии. В самом деле,точно такая же сборка, используете ли вы циклы или рекурсию. Единственный раз, когда компилятор будет (в некоторой степени) обязан генерировать ассемблер, как то, что описывает Йохан, это когда вы делаете что-то, что в любом случае не выражается циклом. Как показано в статье Стила и продемонстрировано практикой использования таких языков, как Haskell, Scheme и SML, не так уж и редко бывает, что хвостовые вызовы можно «оптимизировать», они всегда могутбыть "оптимизированным". Будет ли конкретное использование рекурсии выполняться в постоянном пространстве, зависит от того, как она написана, но ограничения, которые необходимо применить, чтобы сделать это возможным, - это ограничения, которые вам понадобятся, чтобы привести вашу проблему в форму цикла. (На самом деле они менее строгие. Существуют проблемы, такие как конечные автоматы кодирования, которые более аккуратно и эффективно обрабатываются с помощью вызовов tails, а не циклов, для которых потребуются вспомогательные переменные.) Опять же, единственная рекурсия времени требует выполнения большей работы: когда ваш код в любом случае не является циклом.

Я предполагаю, что Йохан имеет в виду компиляторы C, которые имеют произвольные ограничения на то, когда он будет выполнять «оптимизацию» хвостового вызова. Йохан также, по-видимому, ссылается на такие языки, как C ++ и Rust, когда говорит о «языках с управляемыми типами». RAII идиома от C ++ и присутствует в ржавчине , а также делают вещи , которые внешне выглядят как хвостовые вызовы, а не хвост вызовов (потому что «разрушители» еще нужно назвать). Были предложения использовать другой синтаксис для включения немного другой семантики, которая позволила бы хвостовую рекурсию (а именно вызывать деструкторы допоследний вызов хвоста и, очевидно, запретить доступ к "уничтоженным" объектам). (Сборка мусора не имеет такой проблемы, и все Haskell, SML и Scheme являются языками сборки мусора.) В некоторых отношениях некоторые языки, такие как Smalltalk, представляют «стек» как объект первого класса, в этих В таких случаях «стек» больше не является деталью реализации, хотя это не исключает наличия отдельных типов вызовов с различной семантикой. (Java говорит, что не может из-за того, как обрабатывает некоторые аспекты безопасности, но на самом деле это неверно .)

На практике распространенность нарушенных реализаций вызовов функций обусловлена ​​тремя основными факторами. Во-первых, многие языки наследуют сломанную реализацию от языка реализации (обычно C). Во-вторых, детерминистическое управление ресурсами приятно и делает проблему более сложной, хотя это предлагают только несколько языков. В-третьих, и, по моему опыту, причина, по которой большинство людей волнуется, заключается в том, что им нужны трассировки стека при возникновении ошибок в целях отладки. Только вторая причина может быть теоретически мотивированной.

Принципиально отличие состоит в том, что рекурсия включает в себя стек, вспомогательную структуру данных, которую вы, вероятно, не хотите, тогда как циклы не делают этого автоматически. Только в редких случаях типичный компилятор может сделать вывод, что стек вообще не нужен.

Если вместо этого вы сравниваете циклы, работающие вручную с выделенным стеком (например, через указатель на кучную память), вы обычно найдете их не быстрее или даже медленнее, чем при использовании аппаратного стека.