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

вы спрашиваете, почему "это не требует стека, чтобы помнить свой обратный адрес".

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

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

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

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

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

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

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

"обычный" рекурсивная функция (2) в кадре стека.

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

• другие возвращаемые значения
• результат функции owns вычисление

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

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

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

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

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

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

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

int factorial (int n) { помощник инт(инт кол-во, инт, накопленные) { если num == 0 возврат накопленный else return helper(num-1, накопленный*num) } вернуть помощника (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)

видите разницу?

хвост Оптимизация вызовов

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

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

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

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

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

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

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

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

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

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

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

вот как компилятор выполняет оптимизацию хвостовой рекурсии.