Насколько я знаю, рекурсия очень изящна, но неэффективна в ООП и процедурного программирования (см. замечательный "Высокий порядок perl", Марк Джейсон Доминус). У меня была информация о том, что в функциональном программировании рекурсия быстрая - ее элегантность и простота. Может ли кто-нибудь подтвердить и, возможно, усилить это? Я думаю с точки зрения XSLT и Haskell (в моем списке следующего языка).
Спасибо
Daniel
Рекурсия хвоста - это итерация в любой достойной функциональной реализации языка. Вот пример использования GHC Haskell. Простая программа для добавления последовательности чисел. Он начинается как состав нескольких рекурсивных функций:
import qualified Data.Vector as U
main = print (U.sum (U.enumFromTo 1 (10000000 :: Int)))
Что компилятор оптимизирует в одну хвостовую рекурсивную функцию (в преобразовании от источника к источнику):
loop x y = case y <= y 10000000 of
False -> x
True -> loop (x + y) (y + 1)
Эта рекурсивная функция затем скомпилируется в прямой цикл:
loop:
.Lc216:
cmpq $10000000,%rsi
jle .Lc219
movq %r14,%rbx
movq (%rbp),%rax
jmp *(%rax)
.Lc219:
addq %rsi,%r14
incq %rsi
jmp loop
Или с базовым компонентом GHC LLVM, к императивному представлению программы применяются дополнительные оптимизации:
loop:
leaq 1(%rsi), %rax
addq %rsi, %r14
cmpq $10000001, %rax
jge .LBB1_5
addq $2, %rsi
addq %rax, %r14
test: # %tailrecurse
cmpq $10000001, %rsi
jl loop
Обратите внимание, как отмечена метка хвоста рекурсивной.
Таким образом, у нас был конвейер рекурсивных функций, которые были скомпилированы с помощью одной хвостовой рекурсивной функции, которая была скомпилирована в один императивный цикл без использования стека. И 8 инструкций в конце.
И поэтому и состав функций, и рекурсия чрезвычайно эффективны в хороших, оптимизирующих языках функций.
ООП/Процессуальные языки обычно помещают данные в стек каждый раз, когда рекурсивный вызов выполняется, поэтому рекурсия не так эффективна, как итерация на этих языках.
В отличие от этого, компиляторы/интерпретаторы для функциональных языков обычно предназначены для оптимизации хвостовой рекурсии как эффективны как итерация:
Рекурсия может потребовать поддержки стека, но хвостовая рекурсия может быть распознана и оптимизирована компилятором в тот же код, который используется для реализации итерации на императивных языках. Стандарт языка программирования Scheme требует реализации для распознавания и оптимизации хвостовой рекурсии. Оптимизация регрессии хвоста может быть реализована путем преобразования программы в стиль продолжения передачи во время компиляции среди других подходов.
what-is-tail-call-optimization и which-languages-support-tail-recursion-optimization имеют более подробную информацию.
Если используемый компилятор поддерживает оптимизацию хвостового вызова, и вы структурируете свой код, чтобы воспользоваться им, рекурсия не является неэффективной.
Из-за предваряющей рекурсии в функциональном программировании компиляторы для функциональных языков с большей вероятностью реализуют оптимизацию хвостового вызова, которая является процедурной.
Существует два основных способа достижения эффективной рекурсии в XSLT:
Есть много ответов, касающихся хвостовой рекурсии, поэтому просто простой пример:
<xsl:function name="my:sum">
<xsl:param name="pAccum" as="xs:double*"/>
<xsl:param name="pNums" as="xs:double*"/>
<xsl:sequence select=
"if(empty($pNums))
then $pAccum
else
my:sum($pAccum + $pNums[1], $pNums[position() >1])
"
/>
</xsl:function>
Можно проверить, что my: sum (0, 1 to 100) оценивается по: 5050.
Вот как можно реализовать функцию sum() в способе DVC:
<xsl:function name="my:sum2">
<xsl:param name="pNums" as="xs:double*"/>
<xsl:sequence select=
"if(empty($pNums))
then 0
else
if(count($pNums) eq 1)
then $pNums[1]
else
for $half in count($pNums) idiv 2
return
my:sum2($pNums[not(position() gt $half)])
+
my:sum2($pNums[position() gt $half])
"
/>
</xsl:function>
Основная идея DVC состоит в том, чтобы разделить входную последовательность на две (обычно) или более части и обрабатывать их независимо друг от друга, а затем объединить результаты для получения результата для общая входная последовательность.
Обратите внимание, что для последовательности элементов N максимальная глубина стека вызовов в любой момент времени не будет превышать log2(N),, что более чем достаточно для большинства практических целей. Например, максимальная глубина стека вызовов при обработке последовательности из 1000000 (1M) элементов будет всего 19.
Несмотря на то, что есть некоторые XSLT-процессоры, которые недостаточно интеллектуальны для распознавания и оптимизации хвостовой рекурсии, DVC-рекурсивный шаблон работает на любом XSLT-процессоре.
Единственное, что я должен добавить к ответам dons, - это то, что многие языки заложники унаследованных условных соглашений. Нигде это не более верно, чем языки, соответствующие стандарту C-вызова на x86: каждый параметр переходит в стек. Функциональные языки передают по крайней мере некоторые параметры в регистрах, и так далее на 32-битных платформах даже не-хвостовые вызовы (которые не могут быть оптимизированы) по-прежнему более эффективны, чем, скажем, в C.
Слава Богу, у x86-64 есть достойная конвенция о вызове C!
Если язык не оптимизирован компилятором, рекурсия, скорее всего, будет медленнее, чем итерация, потому что вместо того, чтобы спускаться по данной полосе движения, что в значительной степени эквивалентно итерации, вам нужно вернуть свои шаги назад после окончания работы.
В противном случае это в значительной степени эквивалентно, за исключением того, что оно может быть намного более элегантным, поскольку вы позволяете компилятору и системе обрабатывать цикл за кулисами. И, конечно, есть задачи (например, обработка древовидных структур), где рекурсия является единственным способом (или, по крайней мере, единственным, что не безнадежно запутано).
Что делает рекурсию быстро на функциональных языках, так это то, что компиляторы могут внутренне преобразовывать рекурсию в итерацию с помощью устранения хвостовой рекурсии (или, более того, исключение хвостового вызова). В принципе, если рекурсивный вызов является последней операцией перед возвратом функции, а возвращаемое значение функции - это рекурсивный вызов, то вместо создания нового фрейма стека программа будет повторно использовать текущий кадр. Переменные аргументов устанавливаются в новые значения, и ПК устанавливается в начало функции.
Использование исключения хвостовой рекурсии требует некоторого осознания программистом. Вы должны убедиться, что ваши рекурсивные вызовы - это фактически хвосты. Например, вот код в OCaml для вычисления факториала:
let rec factorial n =
if n = 0 then
1
else
n * factorial (n - 1)
Устранение хвостового вызова не будет работать прямо здесь, так как после рекурсивного вызова должно выполняться умножение. Однако, если функция была переписана так:
let factorial n =
let rec fac_helper n p =
if n = 0 then
p
else
fac_helper (n - 1) (p * n)
in
fac_helper n 1
Теперь можно использовать исключение хвостового вызова. Это будет преобразовано в нечто подобное (в псевдокоде):
factorial p n =
p = 1
while n > 0
n = n - 1
p = p * n
return p
Этот стиль может показаться нелогичным, но он имеет такой же смысл, как итеративная версия. Каждый шаг вычисления выполняется при вызове рекурсивной функции. Индукционные переменные, такие как p и n выше, которые используются во всем вычислении, объявляются как аргументы.
Следует отметить, что большинство компиляторов как для императивных, так и для функциональных языков используют эту оптимизацию. На самом деле, версия LLVM оптимизации даже позволяет ассоциативные операции между рекурсивным вызовом и возвратом, поэтому вы можете написать первую версию факториала и по-прежнему использовать оптимизацию. Тем не менее, исключение хвостового вызова не поддерживается на JVM, поэтому функциональные языки JVM, такие как Scala, имеют ограниченную поддержку для него.
Не предполагайте, что рекурсия против итерации - это то место, где вы должны обратить внимание.
Как правило, это становится значительным после того, как вы впервые исключили более крупные проблемы с производительностью.