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

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

// tail recursion
int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

int factorial (int n) {
    return fac_times (n, 1);
}

// normal recursion
int factorial (int n) {
    if (n == 0) return 1;
    else return n * factorial(n - 1);
}

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

Ответы

Ответ 1

Компилятор просто может преобразовать этот

int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

в нечто подобное:

int fac_times (int n, int acc) {
label:
    if (n == 0) return acc;
    acc *= n--;
    goto label;
}

Ответ 2

Вы спрашиваете, почему "он не требует, чтобы стек запоминал его обратный адрес".

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

Конкретно, без оптимизации хвостового вызова:

f: ...
   CALL g
   RET
g:
   ...
   RET

В этом случае, когда вызывается g, стек выглядит следующим образом:

   SP ->  Return address of "g"
          Return address of "f"

С другой стороны, при оптимизации хвостового вызова:

f: ...
   JUMP g
g:
   ...
   RET

В этом случае, когда вызывается g, стек выглядит следующим образом:

   SP ->  Return address of "f"

Ясно, что когда g вернется, он вернется в место, откуда был вызван f.

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

Ответ 3

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

// tail recursion
int fac_times (int n, int acc = 1) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

будет компилировать что-то вроде

// accumulator
int fac_times (int n) {
    int acc = 1;
    while (n > 0) {
        acc *= n;
        n -= 1;
    }
    return acc;
}

Ответ 4

В рекурсивной функции должны присутствовать два элемента:

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

"Регулярная" рекурсивная функция сохраняет (2) в кадре стека.

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

Другие возвращаемые значения
Результат вычисления собственных функций

Посмотрите на свой пример:

int factorial (int n) {
    if (n == 0) return 1;
    else return n * factorial(n - 1);
}

Фрейм f (5) "хранит" результат его собственного вычисления (5) и значения f (4), например. Если я вызываю факториал (5), как раз перед тем, как вызовы стека начинают разрушаться, у меня есть:

 [Stack_f(5): return 5 * [Stack_f(4): 4 * [Stack_f(3): 3 * ... [1[1]]

Обратите внимание, что каждый стек хранит, кроме упомянутых значений, всю область действия функции. Таким образом, использование памяти для рекурсивной функции f является O (x), где x - количество рекурсивных вызовов, которые я должен сделать. Итак, если мне нужно 1kb ОЗУ для вычисления factorial (1) или factorial (2), мне нужно ~ 100k для вычисления факториала (100) и т.д.

A Рекурсивная функция хвоста помещает (2) в нее аргументы.

В рекурсии хвоста я передаю результат частичных вычислений в каждом рекурсивном кадре на следующий, используя параметры. Давайте посмотрим на наш факториальный пример: Tail Recursive:

int factorial (int n) { int helper (int num, int accumulated) { если num == 0 возврат накоплен else return helper (num-1, accumulated * num) } return helper (n, 1)
}

Посмотрим на него в факториале (4):

[Stack f(4, 5): Stack f(3, 20): [Stack f(2,60): [Stack f(1, 120): 120]]]]

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

Шаблоны рекурсии

Регулярная рекурсивная функция имеет следующий вид:

type regular(n)
    base_case
    computation
    return (result of computation) combined with (regular(n towards base case))

Чтобы преобразовать его в рекурсию хвоста, мы:

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

Облик:

type tail(n):
    type helper(n, accumulator):
        if n == base case
            return accumulator
        computation
        accumulator = computation combined with accumulator
        return helper(n towards base case, accumulator)
    helper(n, base case)

Посмотрите разницу?

Оптимизация Tail Call

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

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

Ответ 5

Вот простой пример, показывающий, как работают рекурсивные функции:

long f (long n)
{

    if (n == 0) // have we reached the bottom of the ocean ?
        return 0;

    // code executed in the descendence

    return f(n-1) + 1; // recurrence

    // code executed in the ascendence

}

Рекурсия хвоста - это простая рекурсивная функция, где рекурсия выполняется в конце функции, поэтому код не выполняется в ascendence, что помогает большинству компиляторов языков программирования высокого уровня делать так, что называется "Оптимизация регенерации хвоста" , также имеет более сложную оптимизацию, известную как рекурсия хвоста по модулю

Ответ 6

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

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

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

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

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

Ответ 7

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

void tail(int i) {
    if(i<=0) return;
    else {
     system.out.print(i+"");
     tail(i-1);
    }
   }

После выполнения оптимизации приведенный выше код преобразуется ниже.

void tail(int i) {
    blockToJump:{
    if(i<=0) return;
    else {
     system.out.print(i+"");
     i=i-1;
     continue blockToJump;  //jump to the bolckToJump
    }
    }
   }

Вот как компилятор оптимизирует рекурсию хвоста.