Ответ 1

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

И поэтому и состав функций, и рекурсия чрезвычайно эффективны в хороших, оптимизирующих языках функций.

Ответ 2

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

В отличие от этого, компиляторы/интерпретаторы для функциональных языков обычно предназначены для оптимизации хвостовой рекурсии как эффективны как итерация:

Рекурсия может потребовать поддержки стека, но хвостовая рекурсия может быть распознана и оптимизирована компилятором в тот же код, который используется для реализации итерации на императивных языках. Стандарт языка программирования Scheme требует реализации для распознавания и оптимизации хвостовой рекурсии. Оптимизация регрессии хвоста может быть реализована путем преобразования программы в стиль продолжения передачи во время компиляции среди других подходов.

what-is-tail-call-optimization и which-languages-support-tail-recursion-optimization имеют более подробную информацию.

Ответ 3

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

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

Ответ 4

Эффективная рекурсия в XSLT

Существует два основных способа достижения эффективной рекурсии в XSLT:

• Оптимизация хвостохранилища
• Divide and Conquer (DVC)

Есть много ответов, касающихся хвостовой рекурсии, поэтому просто простой пример:

  <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-процессоре.

Ответ 5

Единственное, что я должен добавить к ответам dons, - это то, что многие языки заложники унаследованных условных соглашений. Нигде это не более верно, чем языки, соответствующие стандарту C-вызова на x86: каждый параметр переходит в стек. Функциональные языки передают по крайней мере некоторые параметры в регистрах, и так далее на 32-битных платформах даже не-хвостовые вызовы (которые не могут быть оптимизированы) по-прежнему более эффективны, чем, скажем, в C.

Слава Богу, у x86-64 есть достойная конвенция о вызове C!

Ответ 6

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

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

Ответ 7

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

Использование исключения хвостовой рекурсии требует некоторого осознания программистом. Вы должны убедиться, что ваши рекурсивные вызовы - это фактически хвосты. Например, вот код в 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, имеют ограниченную поддержку для него.

Ответ 8

Не предполагайте, что рекурсия против итерации - это то место, где вы должны обратить внимание.

Как правило, это становится значительным после того, как вы впервые исключили более крупные проблемы с производительностью.