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

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

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

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

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

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

z, возможно, придется уничтожить после возврата из qwerty здесь.

Еще одна вещь - неявное преобразование типов, которое также может происходить в C, но может быть более сложным и распространенным в 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, и sum нужно будет преобразовать его в int.

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

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

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

РЕДАКТИРОВАТЬ:

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

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

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

Хвостовая рекурсия на самом деле не существует на уровне компилятора в C ++.

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

Очевидно, оптимизация хвостовой рекурсии существует как в MSVC ++, так и в GCC. См. этот вопрос для подробностей.

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

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

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

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

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

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

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