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

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

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

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

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

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

Вы спросите, почему «стеку не требуется запоминать свой адрес возврата».

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

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

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) в кадре стека.

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

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

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

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 - количество рекурсивных вызовов, которые мне нужно сделать. Итак, если мне нужен 1 КБ ОЗУ для вычисления факториала (1) или факториала (2), мне нужно ~ 100 КБ для вычисления факториала (100) и так далее.

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

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

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

Посмотрим на его кадры в factorial (4):

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

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

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

Обычная рекурсивная функция выглядит следующим образом:

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 .

Ваш компилятор должен оптимизировать его, или нет.

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

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

}

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

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

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

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

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

Чтобы написать простую рекурсивную функцию

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 * факт (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

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

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

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

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

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

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

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

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