Что такое хвостовая рекурсия?
https://stackoverflow.com/questions/33923
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Начиная изучать lisp, я наткнулся на этот термин хвост-рекурсивный.Что именно это означает?
Решение
Рассмотрим простую функцию, которая добавляет первые 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 нет.
Другие советы
В традиционной рекурсии типичная модель заключается в том, что сначала вы выполняете свои рекурсивные вызовы, а затем берете возвращаемое значение рекурсивного вызова и вычисляете результат. Таким образом, вы не получите результат своих расчетов, пока не вернетесь после каждого рекурсивного вызова.
В хвостовой рекурсии вы сначала выполняете свои вычисления, а затем выполняете рекурсивный вызов, передавая результаты текущего шага следующему рекурсивному шагу. Это приводит к тому, что последний оператор имеет вид (return (params) (рекурсивная функция)) . По сути, возвращаемое значение любого заданного рекурсивного шага совпадает с возвращаемым значением следующего рекурсивного вызова .
Следствием этого является то, что когда вы будете готовы выполнить следующий рекурсивный шаг, вам больше не нужен текущий фрейм стека. Это учитывает некоторую оптимизацию. Фактически, с соответствующим образом написанным компилятором у вас никогда не должно быть переполнения стека snicker с хвостовым рекурсивным вызовом. Просто используйте текущий кадр стека для следующего рекурсивного шага. Я уверен, что Лисп делает это.
Важным моментом является то, что хвостовая рекурсия по существу эквивалентна зацикливанию. Это не просто вопрос оптимизации компилятора, а фундаментальный факт выразительности. Это идет в обе стороны: вы можете взять любой цикл в форме
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) и почему это лучше.
хвостовой вызов [хвостовая рекурсия] - это своего рода готовая одежда как звонок. Хвостовой вызов происходит, когда функция вызывает другой как его последний действие, так что ему больше нечего делать. Например, в следующем коде вызов
gявляется хвостовым вызовом:function f (x) return g(x) endПосле того, как
fвызоветg, больше ничего нет сделать. В таких ситуациях программа не нужно возвращаться к звонящим функция, когда вызываемая функция заканчивается. Поэтому после хвостового вызова программа не должна сохранять какие-либо информация о вызывающей функции в стеке. ...Потому что правильный вызов хвоста не использует стека, нет ограничений на номер "вложенного" Хвост называет это Программа может сделать. Например, мы можем вызовите следующую функцию с любым число в качестве аргумента; это никогда не будет переполнить стек:
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) в этой функции после выполнения рекурсивного вызова. Если вы введете очень большое число, это, вероятно, приведет к переполнению стека.
Используя обычную рекурсию, каждый рекурсивный вызов помещает другую запись в стек вызовов. Когда рекурсия завершена, приложение должно вытащить каждую запись обратно вниз.
При использовании хвостовой рекурсии, в зависимости от языка, компилятор может сворачивать стек до одной записи, поэтому вы экономите место в стеке ... Большой рекурсивный запрос может фактически вызвать переполнение стека.
В основном рекурсии Tail могут быть оптимизированы в итерацию.
Вместо объяснения словами, вот пример. Это версия Scheme факториальной функции:
(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))))
В первой версии вы заметите, что рекурсивный вызов факта подается в выражение умножения, и поэтому при выполнении рекурсивного вызова состояние должно быть сохранено в стеке. В хвостовой рекурсивной версии нет другого S-выражения, ожидающего значение рекурсивного вызова, и, поскольку дальнейших действий не требуется, состояние не нужно сохранять в стеке. Как правило, хвостовые рекурсивные функции Scheme используют постоянное пространство стека.
В файле жаргона говорится об определении хвостовой рекурсии:
хвостовая рекурсия / n ./
Если вы уже не устали от этого, посмотрите рекурсию хвоста.
Хвостовая рекурсия относится к рекурсивному вызову, который является последним в последней логической инструкции в рекурсивном алгоритме.
Как правило, в рекурсии у вас есть базовый случай , который останавливает рекурсивные вызовы и начинает выталкивать стек вызовов. Чтобы использовать классический пример, хотя и больше C-ish, чем Lisp, функция факториала иллюстрирует хвостовую рекурсию. Рекурсивный вызов происходит после проверки условия базового случая.
factorial(x, fac=1) {
if (x == 1)
return fac;
else
return factorial(x-1, x*fac);
}
Первоначальный вызов факториала будет factorial (n) , где fac = 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);
}
}
Лучший способ для меня понять tail call recursion является частным случаем рекурсии, когда последний звонок(или конечный вызов) - это сама функция.
Сравнение примеров, приведенных на 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).
Редактировать
ПРИМЕЧАНИЕ.Имейте в виду, что приведенный выше пример написан на Python, среда выполнения которого не поддерживает TCO.Это всего лишь пример, объясняющий суть дела.TCO поддерживается на таких языках, как Scheme, Haskell и т. Д
В 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);
}
Вот пример Common Lisp, который выполняет факториалы с использованием хвостовой рекурсии. Из-за природы без стеков можно выполнять безумно большие факторные вычисления ...
(defun ! (n &optional (product 1))
(if (zerop n) product
(! (1- n) (* product n))))
А потом для развлечения вы можете попробовать (формат nil " ~ R " (! 25))
Я не программист на Лиспе, но я думаю, что это поможет.
По сути, это стиль программирования, при котором рекурсивный вызов - это последнее, что вы делаете.
Короче говоря, хвостовая рекурсия имеет рекурсивный вызов как последний оператор в функции, поэтому ей не нужно ждать рекурсивного вызова.
Итак, это хвостовая рекурсия, т. е. 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);
}
Я написал длинный пост под названием " Понимание хвоста Рекурсия & # 8211; Visual Studio C ++ & # 8211; Сборочный вид "
вот версия 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
}
Это выдержка из Структура и интерпретация компьютерных программ о хвостовой рекурсии.
Противопоставляя итерацию и рекурсию, мы должны быть осторожны, чтобы не путать понятие рекурсивного процесса с понятием рекурсивной процедуры.Когда мы описываем процедуру как рекурсивную, мы ссылаемся на синтаксический факт, что определение процедуры ссылается (прямо или косвенно) на саму процедуру.Но когда мы описываем процесс как следующий шаблону, который является, скажем, линейно рекурсивным, мы говорим о том, как развивается процесс, а не о синтаксисе написания процедуры.Может показаться тревожным, что мы ссылаемся на рекурсивную процедуру, такую как fact-iter, как генерирующую итеративный процесс.Однако этот процесс действительно является итеративным:Его состояние полностью фиксируется тремя переменными состояния, и интерпретатору необходимо отслеживать только три переменные, чтобы выполнить процесс.
Одна из причин, по которой различие между процессом и procedure может быть запутанным, заключается в том, что большинство реализаций распространенных языков (включая Ada, Pascal и C) спроектированы таким образом, что интерпретация любого рекурсивного процедура потребляет объем памяти, который растет с увеличением числа вызовов процедуры, даже если описанный процесс в принципе является итеративным.Как следствие, эти языки могут описывать итеративные процессы, только прибегая к специальным “циклическим конструкциям” таким как do, repeat, until, for и while. Реализация Scheme не имеет этого недостатка.Это выполнит итерационный процесс в постоянном пространстве, даже если итерационный процесс описывается рекурсивной процедурой. Реализация с этим свойством называется хвостовой рекурсией. С хвостово-рекурсивной реализацией итерация может быть выражена с использованием обычного механизма вызова процедуры, так что специальные итерационные конструкции полезны только как синтаксический сахар.
Хвостовая рекурсия - это жизнь, которой вы живете прямо сейчас. Вы постоянно перерабатываете один и тот же кадр стека снова и снова, потому что нет причин или средств для возврата к «предыдущему» Рамка. С прошлым покончено, и с ним можно отказаться. Вы получаете один кадр, навсегда двигаясь в будущее, пока ваш процесс неизбежно не умрет.
Аналогия нарушается, если учесть, что некоторые процессы могут использовать дополнительные кадры, но все еще считаются хвостово-рекурсивными, если стек не растет бесконечно.
Хвостовая рекурсия - это рекурсивная функция, в которой функция вызывает сам в конце («хвост») функции, в которой нет вычислений сделано после возврата рекурсивного вызова. Многие компиляторы оптимизируют для заменить рекурсивный вызов на хвостовой рекурсивный или итеративный вызов.
Рассмотрим проблему вычисления факториала числа.
Простой подход будет следующим:
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), но ни один из вызовов не добавляет никакой дополнительной переменной в стек. Следовательно, компилятор может покончить со стеком.
Чтобы понять некоторые основные различия между рекурсией хвостового вызова и рекурсией не хвостового вызова, мы можем исследовать реализации этих технологий в .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 .
Существует два основных типа рекурсии: рекурсия головы и хвостовая рекурсия.
В head recursion функция выполняет рекурсивный вызов, а затем выполняет еще несколько вычислений, возможно, используя результат рекурсивный вызов, например.
В функции хвостовой рекурсии все вычисления выполняются первыми и рекурсивный вызов - это последнее, что происходит.
Взято из этой супер-классной публикации , Пожалуйста, подумайте.
Рекурсия означает функцию, вызывающую себя. Например:
(define (un-ended name)
(un-ended 'me)
(print "How can I get here?"))
Tail-Recursion означает рекурсию, завершающую функцию:
(define (un-ended name)
(print "hello")
(un-ended 'me))
Видите, последнее, что делает незавершенная функция (процедура на жаргоне Scheme), - это вызывает себя. Еще один (более полезный) пример:
(define (map lst op)
(define (helper done left)
(if (nil? left)
done
(helper (cons (op (car left))
done)
(cdr left))))
(reverse (helper '() lst)))
В вспомогательной процедуре последнее, что она делает, если left не равно nil, - это вызывает себя (ПОСЛЕ того, что что-то минует и что-то cdr). Это в основном то, как вы отображаете список.
Хвостовая рекурсия имеет большое преимущество, заключающееся в том, что интерпретатор (или компилятор, зависящий от языка и поставщика) может оптимизировать его и преобразовать в нечто, эквивалентное циклу while. Фактически, в традиции Схемы, большинство "для" и "пока" цикл выполняется методом хвостовой рекурсии (пока, насколько я знаю, пока нет).
На этот вопрос есть много отличных ответов...но я не могу не предложить альтернативный подход к определению "хвостовой рекурсии" или, по крайней мере, "правильной хвостовой рекурсии". А именно:следует ли рассматривать это как свойство определенного выражения в программе?Или следует рассматривать это как свойство реализация языка программирования?
Подробнее о последнем представлении читайте в классическом бумага Уилл Клингер, "Правильная хвостовая рекурсия и эффективность использования пространства" (PLDI 1998), который определил "правильную хвостовую рекурсию" как свойство реализации языка программирования.Определение построено таким образом, чтобы позволить игнорировать детали реализации (например, действительно ли стек вызовов представлен через стек времени выполнения или через выделенный из кучи связанный список фреймов).
Для достижения этой цели он использует асимптотический анализ:не от времени выполнения программы, как это обычно бывает, а скорее от программы использование пространства.Таким образом, использование пространства связанного списка, выделенного из кучи, по сравнению со стеком вызовов среды выполнения оказывается асимптотически эквивалентным;таким образом, приходится игнорировать эту деталь реализации языка программирования (деталь, которая, безусловно, имеет большое значение на практике, но может немного запутать ситуацию, когда кто-то пытается определить, удовлетворяет ли данная реализация требованию быть "рекурсивной по свойствам")
Этот документ заслуживает тщательного изучения по ряду причин:
Это дает индуктивное определение выражения хвоста и хвост зовет программы.(Такое определение и почему такие вызовы важны, по-видимому, являются предметом большинства других ответов, приведенных здесь . )
Вот эти определения, просто для того, чтобы дать представление о тексте:
Определение 1 Тот Самый выражения хвоста части программы, написанной на базовой схеме, определяются индуктивно следующим образом.
- Тело лямбда-выражения - это хвостовое выражение
- Если
(if E0 E1 E2)является хвостовым выражением, тогда обаE1иE2являются хвостовыми выражениями. - Ничто другое не является выражением хвоста.
Определение 2 A вызов хвоста это конечное выражение, которое является вызовом процедуры.
(хвостовой рекурсивный вызов, или, как говорится в документе, "самостоятельный хвостовой вызов" - это частный случай хвостового вызова, когда процедура вызывается сама.)
Он предоставляет формальные определения для шести различных "машин" для оценки базовой схемы, где каждая машина имеет одинаковое наблюдаемое поведение за исключением для асимптотический класс сложности пространства, к которому относится каждый из них.
Например, после приведения определений для машин с соответствующим значением 1.управление памятью на основе стека, 2.сбор мусора, но никаких хвостовых вызовов, 3.сбор мусора и завершающие вызовы, статья продолжается еще более продвинутыми стратегиями управления хранилищем, такими как 4."evlis tail recursion", где среду не нужно сохранять при вычислении последнего аргумента подвыражения в конечном вызове, 5.сведение условий закрытия к просто свободные переменные этого замыкания, и 6.так называемая семантика "безопасного пространства", определенная Аппель и Шао.
Чтобы доказать, что машины на самом деле принадлежат к шести различным классам сложности пространства, в статье для каждой пары сравниваемых машин приводятся конкретные примеры программ, которые будут демонстрировать асимптотическое расширение пространства на одной машине, но не на другой.
(Перечитывая сейчас свой ответ, я не уверен, удалось ли мне на самом деле уловить важнейшие моменты Клейкая бумага.Но, увы, прямо сейчас я не могу посвятить больше времени разработке этого ответа.)
Рекурсивная функция - это функция, которая вызывает сама по себе
Это позволяет программистам писать эффективные программы, используя минимальный объем кода .
Недостатком является то, что они могут вызывать бесконечные циклы и другие неожиданные результаты, если написано неправильно .
Я объясню и простую рекурсивную функцию, и хвостовую рекурсивную функцию
Чтобы написать простую рекурсивную функцию
<Ол>Из приведенного примера:
public static int fact(int n){
if(n <=1)
return 1;
else
return n * fact(n-1);
}
Из приведенного выше примера
if(n <=1)
return 1;
Является ли решающим фактором, когда выходить из цикла
else
return n * fact(n-1);
Является ли фактическая обработка, которая должна быть сделана
Позвольте мне разбить задачу по очереди для облегчения понимания.
Давайте посмотрим, что произойдет внутри, если я запущу fact (4)
public static int fact(4){
if(4 <=1)
return 1;
else
return 4 * fact(4-1);
}
Если цикл завершается ошибкой, он переходит в цикл else
поэтому он возвращает 4 * fact (3)
-
В стековой памяти у нас есть
4 * fact (3)Подставляя n = 3
-
В стековой памяти у нас есть
4 * 3 * fact (2)Подставляя n = 2
-
В стековой памяти у нас есть
4 * 3 * 2 * fact (1)Подставляя n = 1
- Подставляя n = 4
-
В стековой памяти у нас есть
fact (3, 4)Подставляя n = 3
-
В стековой памяти у нас есть
fact (2, 12)Подставляя n = 2
-
В стековой памяти у нас есть
fact (1, 24)Подставляя n = 1
public static int fact(3){
if(3 <=1)
return 1;
else
return 3 * fact(3-1);
}
Если цикл завершается ошибкой, он переходит в цикл else
, поэтому он возвращает 3 * fact (2)
Помните, мы назвали `` `4 * fact (3)` `
Вывод для fact (3) = 3 * fact (2)
Пока в стеке есть 4 * fact (3) = 4 * 3 * fact (2)
public static int fact(2){
if(2 <=1)
return 1;
else
return 2 * fact(2-1);
}
Если цикл завершается ошибкой, он переходит в цикл else
, поэтому он возвращает 2 * fact (1)
Помните, что мы назвали 4 * 3 * fact (2)
Вывод для fact (2) = 2 * fact (1)
Пока в стеке есть 4 * 3 * fact (2) = 4 * 3 * 2 * fact (1)
public static int fact(1){
if(1 <=1)
return 1;
else
return 1 * fact(1-1);
}
If истинен
, поэтому он возвращает 1
Помните, что мы назвали 4 * 3 * 2 * fact (1)
Вывод для fact (1) = 1
Пока что стек имеет 4 * 3 * 2 * fact (1) = 4 * 3 * 2 * 1
Наконец, результат fact (4) = 4 * 3 * 2 * 1 = 24
Хвостовая рекурсия будет
public static int fact(x, running_total=1) {
if (x==1) {
return running_total;
} else {
return fact(x-1, running_total*x);
}
}
public static int fact(4, running_total=1) {
if (x==1) {
return running_total;
} else {
return fact(4-1, running_total*4);
}
}
Если цикл завершается ошибкой, он переходит в цикл else
поэтому он возвращает fact (3, 4)
public static int fact(3, running_total=4) {
if (x==1) {
return running_total;
} else {
return fact(3-1, 4*3);
}
}
Если цикл завершается ошибкой, он переходит в цикл else
, поэтому он возвращает fact (2, 12)
public static int fact(2, running_total=12) {
if (x==1) {
return running_total;
} else {
return fact(2-1, 12*2);
}
}
Если цикл завершается ошибкой, он переходит в цикл else
, поэтому он возвращает fact (1, 24)
public static int fact(1, running_total=24) {
if (x==1) {
return running_total;
} else {
return fact(1-1, 24*1);
}
}
If истинен
, поэтому он возвращает running_total
Вывод для running_total = 24
Наконец, результат fact (4,1) = 24
A хвост рекурсивный функция - это рекурсивная функция, где последняя операция, которую она выполняет перед возвратом, - это вызов рекурсивной функции.То есть возвращаемое значение рекурсивного вызова функции возвращается немедленно.Например, ваш код будет выглядеть следующим образом:
def recursiveFunction(some_params):
# some code here
return recursiveFunction(some_args)
# no code after the return statement
Компиляторы и интерпретаторы, реализующие оптимизация конечных вызовов или устранение хвостового вызова может оптимизировать рекурсивный код для предотвращения переполнения стека.Если ваш компилятор или интерпретатор не реализует оптимизацию конечных вызовов (например, интерпретатор CPython), то нет никакой дополнительной выгоды в написании вашего кода таким образом.
Например, это стандартная рекурсивная факториальная функция в Python:
def factorial(number):
if number == 1:
# BASE CASE
return 1
else:
# RECURSIVE CASE
# Note that `number *` happens *after* the recursive call.
# This means that this is *not* tail call recursion.
return number * factorial(number - 1)
И это рекурсивная версия факториальной функции с конечным вызовом:
def factorial(number, accumulator=1):
if number == 0:
# BASE CASE
return accumulator
else:
# RECURSIVE CASE
# There's no code after the recursive call.
# This is tail call recursion:
return factorial(number - 1, number * accumulator)
print(factorial(5))
(Обратите внимание, что, хотя это код на Python, интерпретатор CPython не выполняет оптимизацию конечных вызовов, поэтому такая организация вашего кода не дает никаких преимуществ во время выполнения.)
Возможно, вам придется сделать свой код немного более нечитаемым, чтобы использовать оптимизацию конечных вызовов, как показано в факториальном примере.(Например, базовый вариант теперь немного неинтуитивен, и accumulator параметр эффективно используется как своего рода глобальная переменная.)
Но преимущество оптимизации конечных вызовов заключается в том, что она предотвращает ошибки переполнения стека.(Я отмечу, что вы можете получить то же самое преимущество, используя итеративный алгоритм вместо рекурсивного.)
Переполнение стека возникает, когда в стек вызовов было помещено слишком много объектов фрейма.Объект frame помещается в стек вызовов при вызове функции и извлекается из стека вызовов при возврате функции.Объекты фрейма содержат такую информацию, как локальные переменные и к какой строке кода возвращаться при возврате функции.
Если ваша рекурсивная функция выполняет слишком много рекурсивных вызовов без возврата, стек вызовов может превысить лимит объекта frame.(Количество зависит от платформы;в Python по умолчанию это 1000 фреймовых объектов.) Это приводит к переполнение стека ошибка.(Эй, так вот откуда взялось название этого сайта!)
Однако, если последнее, что делает ваша рекурсивная функция, это выполняет рекурсивный вызов и возвращает возвращаемое значение, то нет причин, по которым ей нужно сохранять текущий объект frame, который должен оставаться в стеке вызовов.В конце концов, если после рекурсивного вызова функции нет кода, нет причин привязываться к локальным переменным текущего объекта frame.Таким образом, мы можем немедленно избавиться от текущего объекта frame, а не сохранять его в стеке вызовов.Конечным результатом этого является то, что ваш стек вызовов не увеличивается в размерах и, следовательно, не может переполнить стек.
Компилятор или интерпретатор должен иметь оптимизацию хвостовых вызовов в качестве функции, чтобы иметь возможность распознавать, когда может быть применена оптимизация хвостовых вызовов.Даже в этом случае вам, возможно, придется изменить код в вашей рекурсивной функции, чтобы использовать оптимизацию конечных вызовов, и вам решать, стоит ли это потенциальное снижение читабельности оптимизации.
Хвостовая рекурсия довольно быстрая по сравнению с обычной рекурсией. Это быстро, потому что вывод вызова предков не будет записан в стек, чтобы сохранить трек. Но в обычной рекурсии все предки вызывают вывод, записанный в стеке, чтобы сохранить отслеживание.
