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

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

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

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

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

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);
}

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

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

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

function f (x)
  return g(x)
end

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

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

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

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

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

с помощью хвостовой рекурсии компилятор может свернуть стек до одной записи, поэтому вы экономите пространство стека...Большой рекурсивный запрос может вызвать переполнение стека.

в основном хвостовые рекурсии могут быть оптимизированы в итерации.

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

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

вот версия факториала, которая является хвостовой рекурсивной:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

файл жаргона имеет это сказать об определении хвостовой рекурсии:

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

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

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

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

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

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

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

Я написал блог сообщение по теме, в котором есть графические примеры того, как выглядят кадры стека.

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

очень простой и понятный для понимания.

простой способ узнать, является ли рекурсивная функция хвостовой рекурсивной, если она возвращает конкретное значение в базовом случае. Это означает, что он не возвращает 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);
    }
}

в 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);
}

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

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

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

^рекурсии

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) что означает последний вызов самого метода, а не работы после этого.

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

EDIT

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

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

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

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

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

таким образом, это хвостовая рекурсия, т. е. N(x - 1, p * x) является последним утверждением в функции, где компилятор умен, чтобы выяснить, что он может быть оптимизирован для цикла for (факториал). Второй параметр 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++ - Assembly View"

вот 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
}

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

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

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

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

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

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

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

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

существует два основных вида рекурсии:глава рекурсии и хвостовая рекурсия.

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

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

принято от этой супер офигенный пост. Пожалуйста, прочтите это.

рекурсия означает функцию, вызывающую саму себя. Например:

(define (un-ended name)
  (un-ended 'me)
  (print "How can I get here?"))

хвост-рекурсия означает рекурсию, которая завершает функцию:

(define (un-ended name)
  (print "hello")
  (un-ended 'me))

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

(define (map lst op)
  (define (helper done left)
    (if (nil? left)
        done
        (helper (cons (op (car left))
                      done)
                (cdr left))))
  (reverse (helper '() lst)))

в вспомогательной процедуре последнее, что он делает, если left не равен нулю, - это называть себя (после cons something и cdr something). Это в основном, как вы по карте список.

хвостовая рекурсия имеет большое преимущество, что interperter (или компилятор, зависящий от языка и поставщика) может оптимизировать его и преобразовать в нечто эквивалентное циклу while. По сути, в схемной традиции большинство циклов" for "и" while " выполняется в хвостовой рекурсии (насколько я знаю, нет for and while).

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

для получения дополнительной информации о последнем представлении, есть классический статьи by Will Clinger, " правильная хвостовая рекурсия и эффективность пространства "(PLDI 1998), которая определила" правильную хвостовую рекурсию " как свойство реализации языка программирования. Определение построено так, чтобы можно было игнорировать детали реализации (например, действительно ли стек вызовов представлен через стек времени выполнения или через выделенный кучей связанный список кадров).

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

статья стоит тщательного изучения для ряда причины:

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

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

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

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

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

(хвост рекурсивный вызов, или как говорится в документе, "self-tail call" является частным случаем хвостового вызова, когда процедура вызывается сама.)

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

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

---

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

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

рассмотрим задачу вычисления факториала числа.

простой подход будет заключаться в:

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