Ответ 1

Простая хвостовая рекурсивная функция:

unsigned int f( unsigned int a ) {
   if ( a == 0 ) {
      return a;
   }
   return f( a - 1 );   // tail recursion
}

Рекурсия хвоста - это в основном, когда:

• существует только один рекурсивный вызов
• этот вызов является последним в функции

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

Ответ 2

Возвращение хвоста в С++ выглядит так же, как C или любой другой язык.

void countdown( int count ) {
    if ( count ) return countdown( count - 1 );
}

Рекурсия хвоста (и вызов хвоста в целом) требует очистки кадра стека вызывающего абонента перед выполнением хвостового вызова. Для программиста хвостовая рекурсия похожа на цикл, при этом return сводится к работе как goto first_line;. Однако компилятор должен определить, что вы делаете, и если этого не произойдет, все равно будет добавлен дополнительный стек кадров. Большинство компиляторов поддерживают его, но писать цикл или goto обычно проще и менее рискованно.

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

Обратите внимание, что в С++ не может быть объекта с нетривиальным деструктором в области оператора return. Для очистки по окончании функции требуется, чтобы вызывающий абонент возвращался обратно к вызывающему абоненту, устраняя хвостовой вызов.

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

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

Ответ 3

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

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

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

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

int sum(int a[], unsigned len) {
     if (len==0) {
         return 0;
     }
     return a[0] + sum(a+1,len-1);
}

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

Если вы это сделали:

static int sum_helper(int acc, unsigned len, int a[]) {
     if (len == 0) {
        return acc;
     }
     return sum_helper(acc+a[0], len-1, a+1);
}
int sum(int a[], unsigned len) {
     return sum_helper(0, len, a);
}

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

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

int boo(yin * x, yang *y) {
    dharma z = x->foo() + y->bar();
    return z.baz();
}

В этом примере вызов baz на самом деле не является хвостовым вызовом, так как z следует уничтожить после возврата из baz. Я считаю, что правила С++ могут затруднить оптимизацию даже в тех случаях, когда переменная не требуется в течение всего времени вызова, например:

int boo(yin * x, yang *y) {
    dharma z = x->foo() + y->bar();
    int u = z.baz();
    return qwerty(u);
}

z может быть разрушено после возврата из qwerty здесь.

Еще одна вещь - это неявное преобразование типов, которое также может происходить и в C, но может быть более сложным и распространенным в С++. Например:

static double sum_helper(double acc, unsigned len, double a[]) {
     if (len == 0) {
        return acc;
     }
     return sum_helper(acc+a[0], len-1, a+1);
}
int sum(double a[], unsigned len) {
     return sum_helper(0.0, len, a);
}

Здесь вызов суммы sum_helper не является хвостовым вызовом, потому что sum_helper возвращает double, и сумма должна будет преобразовать его в int.

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

bool write_it(int it) {
      return cout << it;
}

Здесь есть вызов, сделанный для cout.operator < как последнее утверждение. cout вернет ссылку на себя (поэтому вы можете вставлять множество вещей вместе в список, разделенный символом < <), который затем принудительно оценивается как bool, который заканчивается вызовом другого метода cout, оператора BOOL(). Этот cout.operator bool() может быть вызван в качестве хвостового вызова в этом случае, но оператор < < не мог.

EDIT:

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

Ответ 4

Рекурсия хвоста на самом деле не существует на уровне компилятора в С++.Забастовкa >

Хотя вы можете писать программы, которые используют хвостовую рекурсию, вы не получаете наследуемых преимуществ хвостовой рекурсии, реализованных путем поддержки компиляторов/интерпретаторов/языков. Например, схема поддерживает оптимизацию хвостовой рекурсии, так что она в основном изменит рекурсию на итерацию. Это делает его более быстрым и неуязвимым для. У С++ такого нет. (наименее не компилятор, который я видел)

По-видимому, оптимизация хвостовой рекурсии существует как в MSVС++, так и в GCC. Подробнее см. этот вопрос.

Ответ 5

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

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

Ответ 6

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

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

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

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

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

Возьмем, например, вычисление степени 10, которая тривиальна и может быть записана петлей.

Должно выглядеть что-то вроде

template<typename T> T pow10(T const p, T const res =1)
{
return p ? res: pow10(--p,10*res);
}

Это дает выполнение, например, 4:

RET, р, разреш

-, 4,1

-, 3,10

-, 2100

-, 1,1000

-, 0,10000

10000, -, -

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

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

template<int N,int R=1> struct powc10
{
int operator()() const
{
return  powc10<N-1, 10*R>()();
}
};

template<int R> struct powc10<0,R>
{

int operator()() const
{
return  R;
}

};

это можно использовать как powc10<10>()() для вычисления 10-й мощности во время компиляции.

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