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

Ответ 1

Рассмотрим простую функцию, которая добавляет первые 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, поскольку интерпретаторы Python не поддерживают оптимизацию хвостового вызова. Однако, хотя оптимизация хвостовых вызовов является частью спецификации ECMAScript 2015, большинство интерпретаторов JavaScript не поддерживают ее.

Ответ 2

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

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

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

Ответ 3

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

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

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

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

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

Ответ 4

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

Ответ 5

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

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

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

Ответ 6

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

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

Ответ 7

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

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

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

Ответ 8

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

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

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

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

Ответ 9

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

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

Ответ 10

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

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

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

Ответ 11

Лучший способ понять 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).

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

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

Ответ 12

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

Ответ 13

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

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

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

Ответ 14

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

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

Ответ 15

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

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

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

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

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 С++ - Сборочный вид"

Ответ 16

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

Ответ 17

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

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

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

Ответ 18

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

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

Ответ 19

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

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

Прямым подходом будет:

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

Ответ 20

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

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

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

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

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

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

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

Ответ 21

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

(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. На самом деле, в традиции Scheme, большинство циклов for и while выполняется методом хвостовой рекурсии (насколько я знаю, нет и for, и while).

Ответ 22

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

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

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

Взято из этого супер классного поста. Пожалуйста, подумайте над прочтением.

Ответ 23

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 24

Рекурсивная функция - это функция, которая вызывает сама

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

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

Я объясню и простую рекурсивную функцию, и хвостовую рекурсивную функцию

Для того, чтобы написать простую рекурсивную функцию

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

Из приведенного примера:

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)

1. Подставляя n = 4

public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

If цикл завершается неудачно, он переходит к циклу else поэтому возвращает 4 * fact(3)

2. В стековой памяти у нас есть 4 * fact(3)

   Подставляя n = 3

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

If цикл завершается неудачей, он переходит в else цикл

поэтому он возвращает 3 * fact(2)

Помните, что мы назвали '' '4 * fact (3)' '

Выход для fact(3) = 3 * fact(2)

Пока стек имеет 4 * fact(3) = 4 * 3 * fact(2)

3. В стековой памяти мы имеем 4 * 3 * fact(2)

   Подставляя n = 2

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

If цикл завершается неудачей, он переходит в else цикл

так что возвращает 2 * fact(1)

Помните, что мы назвали 4 * 3 * fact(2)

Выход для fact(2) = 2 * fact(1)

Пока в стеке есть 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

3. В стековой памяти у нас есть 4 * 3 * 2 * fact(1)

   Подставляя n = 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

Наконец, результат факта (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);
    }
}

1. Подставляя n = 4

public static int fact(4, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(4-1, running_total*4);
    }
}

If цикл завершается неудачно, он переходит в else цикл, поэтому возвращает fact(3, 4)

2. В стековой памяти мы имеем fact(3, 4)

   Подставляя n = 3

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

If цикл завершается неудачей, он переходит в else цикл

так что возвращает fact(2, 12)

2. В стековой памяти мы имеем fact(2, 12)

   Подставляя n = 2

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

If цикл завершается неудачей, он переходит в else цикл

так что возвращает fact(1, 24)

3. В стековой памяти у нас есть fact(1, 24)

   Подставляя n = 1

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

Наконец, результат факта (4,1) = 24

Ответ 25

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

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 no code after the recursive call.
        # This is tail call recursion:
        return factorial(number - 1, number * accumulator)
print(factorial(5))

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

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

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

Переполнения стека возникают, когда в стеке вызовов слишком много объектов кадра. Объект кадра помещается в стек вызовов при вызове функции и извлекается из стека вызовов при возврате функции. Объекты Frame содержат информацию, такую как локальные переменные и строку кода, к которой нужно вернуться, когда функция вернется.

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

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

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

Ответ 26

Многие люди уже объяснили рекурсию здесь. Я хотел бы привести пару соображений о некоторых преимуществах, которые дает рекурсия из книги Риккардо Террелла "Параллелизм в .NET, Современные шаблоны параллельного и параллельного программирования":

"Функциональная рекурсия - это естественный способ итерации в FP, поскольку она позволяет избежать изменения состояния. Во время каждой итерации в конструктор цикла передается новое значение, а не обновляется (мутирует). Кроме того, рекурсивная функция может быть составлена, делая Ваша программа более модульная, а также предоставляет возможности для использования распараллеливания. "

Вот также некоторые интересные заметки из той же книги о хвостовой рекурсии:

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

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

Ответ 27

Хвостовая рекурсия довольно быстрая по сравнению с обычной рекурсией. Это быстро, потому что вывод вызова предков не будет записан в стек, чтобы сохранить трек. Но в обычной рекурсии все предки вызывают вывод, записанный в стеке, чтобы сохранить трек.