algorithm - хвостовой - хвостовая рекурсия с++




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

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

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

Прямым подходом было бы:

  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), но ни один из вызовов не добавляет в стек дополнительную дополнительную переменную. Следовательно, компилятор может удалить стек.

В то время как я начинаю изучать lisp, я сталкивался с термином tail-recursive . Что это значит?


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

В хвостовой рекурсии вы сначала выполняете свои вычисления, а затем выполняете рекурсивный вызов, передавая результаты вашего текущего шага на следующий рекурсивный шаг. Это приводит к тому, что последний оператор находится в форме (return (recursive-function params)) . В принципе, возвращаемое значение любого заданного рекурсивного шага совпадает с возвращаемым значением следующего рекурсивного вызова .

Следствием этого является то, что, как только вы готовы выполнить свой следующий рекурсивный шаг, вам больше не нужен текущий стек кадров. Это позволяет оптимизировать. Фактически, с соответствующим образом написанным компилятором, у вас никогда не должно быть сверкающего переполнения стека с хвостовым рекурсивным вызовом. Просто повторите использование текущего кадра стека для следующего рекурсивного шага. Я почти уверен, что Lisp делает это.


В файле жаргона говорится об определении хвостовой рекурсии:

хвостовая рекурсия /n./

Если вы уже не устали от этого, см. Хвостовую рекурсию.


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

while(E) { S }; return Q

где E и Q - выражения, а S - последовательность операторов и превращает ее в хвостовую рекурсивную функцию

f() = if E then { S; return f() } else { return Q }

Конечно, E , S и Q должны быть определены для вычисления некоторого интересного значения по некоторым переменным. Например, функция циклирования

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

эквивалентно хвостовой рекурсивной функции (ей)

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

(Эта «обертка» хвостовой рекурсивной функции с функцией с меньшим количеством параметров является общей функциональной идиомой.)


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

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

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


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

Очень просто и интуитивно понятно.

Легкий способ определить, является ли рекурсивная функция хвостовой рекурсивной, - если она возвращает конкретное значение в базовом случае. Это означает, что он не возвращает 1 или true или что-то в этом роде. Это, скорее всего, вернет некоторый вариант одного из параметров метода.

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

public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);
    }
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
    }
}

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

Таким образом, это хвостовая рекурсия, то есть N (x - 1, p * x) является последним оператором в функции, в которой компилятор умен, чтобы понять, что он может быть оптимизирован для цикла (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);
}

Я написал длинный пост под названием « Understanding Tail Recursion - Visual Studio C ++ - Assembly View »


Лучший способ понять 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) что означает, что последний вызов выполняется самому методу и после операции не выполняется.

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

РЕДАКТИРОВАТЬ

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


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

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


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

Как правило, в рекурсии у вас есть базовый регистр, который останавливает рекурсивные вызовы и начинает выскакивать стек вызовов. Чтобы использовать классический пример, хотя больше C-ish, чем Lisp, факториальная функция иллюстрирует рекурсию хвоста. Рекурсивный вызов возникает после проверки базового условия.

factorial(x, fac) {
  if (x == 1)
     return fac;
   else
     return factorial(x-1, x*fac);
}

Обратите внимание, что начальный вызов факториала должен быть факториальным (n, 1), где n - это число, для которого нужно вычислить факториал.


У этого вопроса есть много отличных ответов ... но я не могу не ответить на альтернативный подход, как определить «рекурсию хвоста» или, по крайней мере, «правильную рекурсию хвоста». А именно: следует ли рассматривать его как свойство определенного выражения в программе? Или следует рассматривать его как свойство реализации языка программирования ?

Более подробно на последнем представлении есть классическая paper Уилла Клингера «Надлежащая рекурсия хвоста и эффективность пространства» (PLDI 1998), которая определила «правильную рекурсию хвоста» как свойство реализации языка программирования. Определение сконструировано так, чтобы можно было игнорировать детали реализации (например, действительно ли стек вызовов фактически представлен через стек выполнения или через связанный с кучей связанный список фреймов).

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

Документ заслуживает тщательного изучения по ряду причин:

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

    Вот эти определения, чтобы обеспечить вкус текста:

    Определение 1 Выражения хвоста программы, записанные в Core Scheme, определяются индуктивно следующим образом.

    1. Тело лямбда-выражения является выражением хвоста
    2. Если (if E0 E1 E2) является хвостовым выражением, то оба E1 и E2 являются хвостовыми выражениями.
    3. Ничто другое не является выражением хвоста.

    Определение 2 Хвост-вызов - это выражение хвоста, которое является вызовом процедуры.

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

  • Он предоставляет формальные определения для шести разных «машин» для оценки Core Scheme, где каждая машина имеет одно и то же наблюдаемое поведение, за исключением класса асимптотической сложности сложности, в котором находится каждый.

    Например, после определения определений для машин соответственно: 1. управление памятью на основе стека, 2. сбор мусора, но отсутствие хвостовых вызовов, 3. сбор мусора и хвостовые звонки, бумага продолжается вперед с еще более продвинутыми стратегиями управления хранением, такими как 4. «evlis tail recursion», где окружающая среда не нуждается в сохранении во время оценки последнего аргумента подвыражения в хвостовом вызове, 5. сокращение среды закрытия до только свободных переменных этого закрытия и 6. так называемая «безопасная для космоса» семантика, как это определено Аппелем и Шао .

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

(Прочитав мой ответ сейчас, я не уверен, что мне удастся фактически зафиксировать ключевые моменты работы paper . Но, увы, я не могу посвятить больше времени на разработку этого ответа прямо сейчас.)


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

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

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

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

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

Если вы хотите прочитать о некоторых различиях в дизайне рекурсии хвостового вызова между C # и F #, см. Раздел «Генерирование кода хвоста в C # и F #» .

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


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

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


Этот отрывок из книги « Программирование в Луа» показывает, как сделать правильную рекурсию хвоста (в Lua, но также следует применять к Lisp) и почему это лучше.

Хвост-вызов [хвостовая рекурсия] - это своего рода гото, одетый как звонок. Хвост вызова происходит, когда функция вызывает другое как последнее действие, поэтому ему больше нечего делать. Например, в следующем коде вызов g является хвостовым вызовом:

function f (x)
  return g(x)
end

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

Поскольку правильный хвостовой вызов не использует пространство стека, нет ограничений на количество «вложенных» хвостовых вызовов, которые может сделать программа. Например, мы можем вызвать следующую функцию с любым числом в качестве аргумента; он никогда не переполнит стек:

function foo (n)
  if n > 0 then return foo(n - 1) end
end

... Как я сказал ранее, хвостовой вызов - это нечто вроде goto. Таким образом, довольно полезное приложение правильных хвостовых вызовов в Lua предназначено для программирования государственных машин. Такие приложения могут представлять каждое состояние функцией; для изменения состояния следует перейти к (или вызвать) конкретную функцию. В качестве примера рассмотрим простую игру в лабиринте. В лабиринте есть несколько комнат, каждая из которых имеет до четырех дверей: север, юг, восток и запад. На каждом шаге пользователь вводит направление движения. Если в этом направлении есть дверь, пользователь переходит в соответствующую комнату; в противном случае программа выводит предупреждение. Цель состоит в том, чтобы перейти от начальной комнаты до последней комнаты.

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

function room1 ()
  local move = io.read()
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room
  end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

Итак, вы видите, когда вы делаете рекурсивный вызов, например:

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

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


вот версия 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
}

Рассмотрим простую функцию, которая добавляет первые N целых чисел. (например, sum(5) = 1 + 2 + 3 + 4 + 5 = 15 ).

Вот простая реализация JavaScript, использующая рекурсию:

function recsum(x) {
    if (x===1) {
        return x;
    } else {
        return x + recsum(x-1);
    }
}

Если вы вызвали recsum(5) , это будет интерпретировать JavaScript-интерпретатор:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

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

Вот рекурсивная версия той же функции:

function tailrecsum(x, running_total=0) {
    if (x===0) {
        return running_total;
    } else {
        return tailrecsum(x-1, running_total+x);
    }
}

Вот последовательность событий, которые произойдут, если вы tailrecsum(5) , что эффективно будет tailrecsum(5, 0) из-за второго аргумента по умолчанию).

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

В хвостовом рекурсивном случае при каждой оценке рекурсивного вызова обновляется running_total .

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





tail-recursion