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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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