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

Question

Пока я начинал изучать шепот, я встретил термин хвост-рекурсив . Что это значит точно?

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

Answer 2

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

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

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

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

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

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

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

Answer 4

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

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

Answer 5

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

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

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

Answer 6

Вместо объяснения словами, вот пример. Это версия 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 используют постоянное пространство стека.

Answer 7

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

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

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

Answer 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 - это число, для которого рассчитывается факториал.

Answer 9

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

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

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