Эффективная рекурсия в функциональном программировании против неэффективной рекурсии в разных парадигмах

Question

Насколько я знаю, рекурсия очень элегантна, но неэффективна в ООП и процедурном программировании (см. Замечательный «Perl высокого порядка», Марк Джейсон Доминус). У меня была информация о том, что в функциональном программировании рекурсия быстрая - сохраняя свою элегантность и простоту. Может ли кто-нибудь подтвердить и, возможно, усилить это? Я думаю с точки зрения XSLT и Haskell (высоко в моем списке следующего языка для изучения)

Спасибо

Daniel

Answer 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 инструкций в конце.

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

Answer 2

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

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

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

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

Answer 3

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

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

Answer 4

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

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

1. Оптимизация хвостовой рекурсии
2. Разделяй и властвуй (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 до 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.

Answer 5

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

Слава Богу, x86-64 имеет приличное соглашение о вызовах C!

Answer 6

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

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

Answer 7

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

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

Answer 8

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

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