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

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

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

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

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

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

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

В процедуре помощника, ПОСЛЕДНЯЯ вещь это делает, если левый не является нолем, должен назвать себя (ПОСЛЕ ТОГО, КАК подставляет что-то и командира что-то). Это в основном, как Вы отображаете список.

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

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

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

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

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

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

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

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

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

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

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

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

В основном Хвостовые рекурсии в состоянии быть оптимизированными в повторение.

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

А последний вызов [хвостовая рекурсия] является своего рода goto, одетым как вызов. Последний вызов происходит, когда вызовы функции другой как его последнее действие, таким образом, он не имеет ничего иного, чтобы сделать. Например, в следующем коде, вызов к 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) в той функции после того, как выполняется рекурсивный вызов. При вводе очень высокого количества, оно, вероятно, вызовет переполнение стека.

Файл жаргона говорит следующее об определении хвостовой рекурсии:

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

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

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

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

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

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

В Java вот является возможный хвост рекурсивной реализацией функции Fibonacci:

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

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

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

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

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