Что такое хвостовая рекурсия?

Question

Пока я начинал изучать шепот, я встретил термин хвост-рекурсив . Что это значит точно?

Answer 1

Лучший способ для меня понять tail call recursion - это особый случай рекурсии, когда последний вызов (или хвостовой вызов) - это сама функция.

Сравнение примеров, представленных в Python:

def recsum(x):
 if x == 1:
  return x
 else:
  return x + recsum(x - 1)

^ RECURSION

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

^ РЕАКЦИЯ ХВОСТА

Как вы можете видеть в общей рекурсивной версии, последний вызов в блоке кода - x + recsum(x - 1). Таким образом, после вызова метода recsum, есть другая операция, которая x + ...

Однако в хвостовой рекурсивной версии последний вызов (или хвостовой вызов) в блоке кода равен tailrecsum(x - 1, running_total + x), что означает, что последний вызов был выполнен для самого метода, и после этого операции не выполнялось.

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

EDIT

NB. Помните, что приведенный выше пример написан на языке Python, среда выполнения которого не поддерживает TCO. Это всего лишь пример, чтобы объяснить суть. TCO поддерживается на таких языках, как Scheme, Haskell и т. Д.

Answer 2

В Java возможна хвостовая рекурсивная реализация функции Фибоначчи:

public int tailRecursive(final int n) {
    if (n <= 2)
        return 1;
    return tailRecursiveAux(n, 1, 1);
}

private int tailRecursiveAux(int n, int iter, int acc) {
    if (iter == n)
        return acc;
    return tailRecursiveAux(n, ++iter, acc + iter);
}

Сравните это со стандартной рекурсивной реализацией:

public int recursive(final int n) {
    if (n <= 2)
        return 1;
    return recursive(n - 1) + recursive(n - 2);
}

Answer 3

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

(defun ! (n &optional (product 1))
    (if (zerop n) product
        (! (1- n) (* product n))))

А потом ради интереса вы можете попробовать (format nil "~R" (! 25))

Answer 4

Я не программист на Лиспе, но я думаю это поможет.

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

Answer 5

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

Так что это хвостовая рекурсия, т. Е. N (x - 1, p * x) - это последний оператор в функции, где компилятор умен, чтобы выяснить, что его можно оптимизировать для цикла for (factorial) Второй параметр p несет значение промежуточного продукта.

function N(x, p) {
   return x == 1 ? p : N(x - 1, p * x);
}

Это нерекурсивный способ написания вышеупомянутой факториальной функции (хотя некоторые компиляторы C ++ в любом случае могут ее оптимизировать).

function N(x) {
   return x == 1 ? 1 : x * N(x - 1);
}

но это не так:

function F(x) {
  if (x == 1) return 0;
  if (x == 2) return 1;
  return F(x - 1) + F(x - 2);
}

Я написал длинный пост под названием « Понимание рекурсии хвоста - Visual Studio C ++ - Представление сборки »

Answer 6

вот версия Perl 5 функции tailrecsum, упомянутой ранее.

sub tail_rec_sum($;$){
  my( $x,$running_total ) = (@_,0);

  return $running_total unless $x;

  @_ = ($x-1,$running_total+$x);
  goto &tail_rec_sum; # throw away current stack frame
}

Answer 7

Это отрывок из Структура и интерпретация компьютерных программ о хвостовой рекурсии.

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

Одна из причин того, что различие между процессом и процедурой может быть сбивает с толку то, что большинство реализаций распространенных языков (включая Ada, Pascal и В) разработаны таким образом, что интерпретация любого рекурсивного процедура потребляет объем памяти, который увеличивается с увеличением количества вызовы процедур, даже если описанный процесс, в принципе, итеративный. Как следствие, эти языки могут описывать итеративный процессы только путем обращения к специальным «циклическим конструкциям» такие, как сделать, повторить, пока, для и в то время. Реализация Схема не разделяет этот дефект. Это выполнит итерационный процесс в постоянном пространстве, даже если Итерационный процесс описывается рекурсивной процедурой. Реализация с этим свойством называется хвостовой рекурсией. хвостовая рекурсивная реализация, итерация может быть выражена с помощью обычный механизм вызова процедуры, так что специальная итерация конструкции полезны только как синтаксический сахар.

Answer 8

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

Рассмотрим проблему вычисления факториала числа.

Простой подход был бы:

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

Предположим, вы звоните факториалом (4). Дерево рекурсии будет:

       factorial(4)
       /        \
      4      factorial(3)
     /             \
    3          factorial(2)
   /                  \
  2                factorial(1)
 /                       \
1                       factorial(0)
                            \
                             1    

Максимальная глубина рекурсии в приведенном выше случае составляет O (n).

Однако рассмотрим следующий пример:

factAux(m,n):
if n==0  then m;
else     factAux(m*n,n-1);

factTail(n):
   return factAux(1,n);

Дерево рекурсии для factTail (4) будет:

factTail(4)
   |
factAux(1,4)
   |
factAux(4,3)
   |
factAux(12,2)
   |
factAux(24,1)
   |
factAux(24,0)
   |
  24

Здесь также максимальная глубина рекурсии равна O (n), но ни один из вызовов не добавляет никакой дополнительной переменной в стек. Следовательно, компилятор может покончить со стеком.

Answer 9

Хвостовая рекурсия - это жизнь, которой вы живете прямо сейчас. Вы постоянно перерабатываете один и тот же кадр стека, снова и снова, потому что нет причин или средств для возврата к «предыдущему» кадру. С прошлым покончено, и с ним можно отказаться. Вы получаете один кадр, навсегда двигаясь в будущее, пока ваш процесс неизбежно не умрет.

_{Аналогия нарушается, если учесть, что некоторые процессы могут использовать дополнительные кадры, но все еще считаются хвостово-рекурсивными, если стек не увеличивается бесконечно.}

Answer 10

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

Вот статья с некоторыми примерами на C #, F # и C ++ \ CLI: Приключения в хвостовой рекурсии на C #, F # и C ++ \ CLI .

C # не оптимизирует для рекурсии хвостового вызова, тогда как F # делает.

Принципиальные различия касаются циклов и лямбда-исчисления. C # разработан с учетом циклов, тогда как F # построен на принципах лямбда-исчисления. За очень хорошую (и бесплатную) книгу о принципах лямбда-исчисления см. Структура и интерпретация компьютерных программ, Абельсон, Суссман и Суссман .

Относительно хвостовых вызовов в F #, для очень хорошей вводной статьи см. Подробное введение в хвостовые вызовы в F # . Наконец, вот статья, в которой рассматривается различие между нехвостовой рекурсией и рекурсией хвостового вызова (в F #): Хвостовая рекурсия по сравнению с нехвостовой рекурсией в F sharp .

Если вы хотите прочитать о некоторых конструктивных различиях рекурсии хвостового вызова между C # и F #, см. Создание кода операции Tail-Call в C # и F # .

Если вам нужно знать, какие условия мешают компилятору C # выполнять оптимизацию хвостового вызова, см. Эту статью: Условия хвостового вызова JIT CLR .