Хвостовая рекурсия является частным случаем хвостового вызова. Хвостовой вызов - это то, где компилятор может увидеть, что нет никаких операций, которые нужно выполнять по возвращении из вызываемой функции - по сути, превращая возвращение вызываемой функции в свою собственную. Компилятор часто может выполнить несколько операций по исправлению стека, а затем перейти (а не вызвать) к адресу первой инструкции вызываемой функции .
Одной из замечательных особенностей этого, помимо устранения некоторых обратных вызовов, является то, что вы также сокращаете использование стека. На некоторых платформах или в коде ОС стек может быть весьма ограничен, а на современных компьютерах, таких как процессоры 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 - переместить значение и очистить регистр или позицию стека. Sum_helper выполняет всю математику.
Поскольку вы упомянули C ++ в своем вопросе, я упомяну некоторые особые вещи по этому поводу.
C ++ скрывает от вас некоторые вещи, которые C не делает. Из этих деструкторов это главное, что встанет на пути оптимизации хвостового вызова.
int boo(yin * x, yang *y) {
dharma z = x->foo() + y->bar();
return z.baz();
}
В этом примере вызов baz на самом деле не является хвостовым вызовом, поскольку после возврата из baz необходимо уничтожить z. Я считаю, что правила 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 для sum_helper не является хвостовым вызовом, потому что sum_helper возвращает значение типа double, и sum необходимо преобразовать его в int.
В C ++ довольно часто возвращают ссылку на объект, которая может иметь различные интерпретации, каждая из которых может быть различным преобразованием типа,
Например:
bool write_it(int it) {
return cout << it;
}
Здесь есть вызов cout.operator << в качестве последнего оператора. cout вернет ссылку на себя (именно поэтому вы можете связать много вещей в список, разделенный <<), который затем вынуждает быть оцененным как bool, который в итоге вызывает другой метод cout, оператор bool ( ). В этом случае этот cout.operator bool () может быть вызван как оконечный вызов, но оператор << не может. </p>
EDIT:
Одна вещь, на которую стоит обратить внимание, это то, что главная причина, по которой возможна оптимизация хвостового вызова в C, заключается в том, что компилятор знает, что вызываемая функция будет хранить свое возвращаемое значение в том же месте, что и вызывающая функция, чтобы гарантировать возвращаемое значение сохраняется в.