Что Такое Оптимизация Хвостового Вызова?

давайте рассмотрим простой пример: факторная функция, реализованная в C.

начнем с очевидного рекурсивного определения

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    return n * fac(n - 1);
}

функция завершается хвостовым вызовом, если последняя операция перед возвратом функции является другим вызовом функции. Если этот вызов вызывает ту же функцию, он является хвостовым рекурсивным.

хотя fac() выглядит хвост-рекурсивный на первый взгляд, это не так что на самом деле происходит

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    unsigned acc = fac(n - 1);
    return n * acc;
}

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

однако, можно переписать fac() чтобы быть хвост-рекурсивным, передавая накопленное значение вниз по цепочке вызовов в качестве дополнительного аргумента и передавая только конечный результат снова в качестве возвращаемого значения:

unsigned fac(unsigned n)
{
    return fac_tailrec(1, n);
}

unsigned fac_tailrec(unsigned acc, unsigned n)
{
    if (n < 2) return acc;
    return fac_tailrec(n * acc, n - 1);
}

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

оптимизация хвостового вызова преобразует наш рекурсивный код в

unsigned fac_tailrec(unsigned acc, unsigned n)
{
TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

это может быть встроено в fac() и мы приходим в

unsigned fac(unsigned n)
{
    unsigned acc = 1;

TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

что эквивалентно

unsigned fac(unsigned n)
{
    unsigned acc = 1;

    for (; n > 1; --n)
        acc *= n;

    return acc;
}

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

TCO (оптимизация хвостового вызова) - это процесс, с помощью которого интеллектуальный компилятор может вызвать функцию и не занимать дополнительное пространство стека. Элемент только ситуация, в которой это происходит, если последняя инструкция выполняется в функции f - это вызов функции g (Примечание: g может быть f). Ключ здесь в том, что f больше не нужно пространство стека - он просто вызывает g а потом возвращает то, что g будет возвращаться. В этом случае оптимизация может быть сделана так, что g просто запускается и возвращает любое значение, которое он будет иметь для того, что называется f.

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

пример: эта факторная функция не является TCOptimizable:

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

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

Это ниже функция TCOptimizable:

def fact_h(n, acc):
    if n == 0:
        return acc
    return fact_h(n-1, acc*n)

def fact(n):
    return fact_h(n, 1)

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

вероятно, лучшее описание высокого уровня, которое я нашел для хвостовых вызовов, рекурсивных хвостовых вызовов и оптимизации хвостовых вызовов, - это сообщение в блоге

"что за черт: хвост вызов"

дан Сугальски. На хвосте оптимизации вызова он пишет:

рассмотрим, на мгновение, эту простую функцию:

sub foo (int a) {
  a += 15;
  return bar(a);
}

Итак, что вы можете сделать, или, скорее, ваш компилятор языка? Ну, что он может сделать, это превратить код форма return somefunc(); в низкоуровневую последовательность pop stack frame; goto somefunc();. В нашем примере это означает, что перед вызовом bar,foo очищает себя, а затем, вместо того, чтобы звонить bar в качестве подпрограммы мы делаем низкоуровневый goto операция до начала bar. Fooуже очистил себя из стека, так что когда bar начинает это выглядит как тот, кто позвонил foo действительно называется bar, и когда bar возвращает его значение, он возвращает его непосредственно тому, кто вызвал foo, а не возвращая его в foo который затем вернет его своему абоненту.

и на хвостовой рекурсии:

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

так что вот так:

sub foo (int a, int b) {
  if (b == 1) {
    return a;
  } else {
    return foo(a*a + a, b - 1);
  }

тихо превращается в:

sub foo (int a, int b) {
  label:
    if (b == 1) {
      return a;
    } else {
      a = a*a + a;
      b = b - 1;
      goto label;
   }

что мне нравится в этом описании, так это то, как лаконично и легко понять для тех, кто исходит из императивного языкового фона (C, C++, Java)

обратите внимание прежде всего, что не все языки поддерживают его.

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

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

смотрите здесь:

http://tratt.net/laurie/tech_articles/articles/tail_call_optimization

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

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

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

3. TCO может вызвать вечно работающую функцию:

   void eternity()
   {
       eternity();
   }
   

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

есть много языков, которые делают TCO, как (Javascript, Ruby и несколько C ), где как Python и Java не делают TCO.

язык JavaScript подтвердил использование :)http://2ality.com/2015/06/tail-call-optimization.html