Ответ 1
Это может помочь вам подумать об этом с точки зрения того, как оптимизация хвостовых вызовов фактически реализована. Конечно, это не часть определения, но оно мотивирует определение.
Обычно, когда вызывается функция, вызывающий код будет хранить любые значения регистра, которые ему понадобятся позже, в стеке. Он также сохранит адрес возврата, указав следующую команду после вызова. Он будет делать все возможное, чтобы убедиться, что указатель стека настроен правильно для вызываемого абонента. Затем он перейдет к целевому адресу [*] (в данном случае, к той же функции). При возврате он знает, что возвращаемое значение находится в месте, указанном соглашением о вызове (слот регистрации или стека).
Для вызова хвоста вызывающий абонент не делает этого. Он игнорирует любые значения регистра, поскольку он знает, что они не понадобятся им позже. Он устанавливает указатель стека так, что вызываемый будет использовать тот же стек, который сделал вызывающий, и он не настроен как обратный адрес, он просто перескакивает на целевой адрес. Таким образом, вызываемый будет перезаписывать одну и ту же область стека, он поместит свое возвращаемое значение в том же месте, в котором вызывающий объект поместил бы его возвращаемое значение, а когда он вернется, он не вернется к своему вызывающему, но вернется к своему вызывающему абоненту вызывающий абонент.
Поэтому, неофициально, функция является хвостовой рекурсивной, когда возможно для оптимизации хвостового вызова, и когда целью хвостового вызова является сама функция. Эффект более или менее такой же, как если бы функция содержала цикл, и вместо того, чтобы называть себя, хвостовой вызов переходит к началу цикла. Это означает, что после вызова не должно быть никаких переменных (и, действительно, нет "работы", которая на языке С++ означает, что ничего не нужно разрушать), а возвращаемое значение хвостового вызова должно быть возвращено вызывающим.
Это все для простой/тривиальной хвостовой рекурсии. Существуют преобразования, которые могут быть использованы для того, чтобы сделать что-то хвостовое рекурсивное, чего еще нет, например, ввести дополнительные параметры, которые хранят некоторую информацию, используемую "самым нижним" уровнем рекурсии, для выполнения работы, которая в противном случае была бы выполнена выход". Так, например:
int triangle(int n) {
if (n == 0) return 0;
return n + triangle(n-1);
}
можно сделать хвост-рекурсивным, либо программистом, либо автоматически с помощью достаточно умного компилятора, например:
int triangle(int n, int accumulator = 0) {
if (n == 0) return accumulator;
return triangle(n-1, accumulator + n);
}
Следовательно, прежняя функция может быть описана как "хвост рекурсивная" тем, кто говорит о достаточно умном языке/компиляторе. Будьте готовы к использованию этого варианта.
[*] Хранение обратного адреса, перемещение указателя стека и перескакивание могут или не могут быть завернуты в один код операции по архитектуре, но даже если это не так, что обычно происходит.