Введение
Подпрограммный вызов, выполняемый как последнее действие процедуры. В информатике хвостовой вызов — это подпрограммный вызов, выполняемый как последнее действие процедуры. Если целью хвостового вызова является та же подпрограмма, то подпрограмма называется хвостовой рекурсией, что является частным случаем прямой рекурсии. Хвостовая рекурсия (или рекурсия в конце хвоста) особенно полезна и часто легко оптимизируется в реализациях. Хвостовые вызовы могут быть реализованы без добавления новой записи в стек вызовов. Большая часть стекового фрейма текущей процедуры больше не требуется и может быть заменена стековым фреймом хвостового вызова, соответствующим образом модифицированным (аналогично наложению для процессов, но для вызовов функций). Затем программа может перейти к вызванной подпрограмме. Создание такого кода вместо стандартной последовательности вызовов называется устранением хвостового вызова или оптимизацией хвостового вызова. Устранение хвостовых вызовов позволяет реализовать вызовы процедур в хвостовой позиции так же эффективно, как операторы `goto`, что обеспечивает эффективное структурированное программирование. По словам Гая Л. Стила, "в общем случае, вызовы процедур можно рассматривать как полезные операторы `goto`, которые также передают параметры и могут быть единообразно закодированы как инструкции `JUMP`".
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recursion (or tail end recursion) is particularly useful, and is often easy to optimize in implementations. Tail calls can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is no longer needed, and can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination or tail call optimization. Tail call elimination allows procedure calls in tail position to be implemented as efficiently as goto statements, thus allowing efficient structured programming. In the words of Guy L. Steele, "in general, procedure calls may be usefully thought of as GOTO statements which also pass parameters, and can be uniformly coded as [machine code] JUMP instructions."
История
В докладе, представленном на конференции ACM в Сиэтле в 1977 году, Гай Л. Стил обобщил дискуссию о GOTO и структурированном программировании и отметил, что вызовы процедур в хвостовой позиции могут быть наиболее эффективно реализованы как прямой переход управления к вызываемой процедуре, обычно избегая ненужных операций с использованием стека. Поскольку такие "хвостовые вызовы" очень распространены в Lisp, языке, где вызовы процедур встречаются повсеместно, эта оптимизация значительно снижает стоимость вызова процедуры по сравнению с другими реализациями. Стил утверждал, что неэффективная реализация вызовов процедур привела к ошибочному представлению о том, что GOTO был более дешёвым, чем вызов процедуры. Стил также утверждал, что "в целом, вызовы процедур можно рассматривать как операторы GOTO, которые также передают параметры, и их можно единообразно кодировать как [машинный код] инструкции JUMP", при этом инструкции машинного кода для работы со стеком следует "считать оптимизацией (а не наоборот!)".
Методы осуществления
Хвостовая рекурсия важна для некоторых языков высокого уровня, особенно функциональных и логических языков, а также для языков семейства Lisp. В этих языках хвостовая рекурсия является наиболее распространенным способом (а иногда и единственным доступным способом) реализации итераций. Спецификация языка Scheme требует оптимизации хвостовых вызовов, чтобы избежать роста стека. В Perl можно выполнять явные хвостовые вызовы, используя вариант инструкции "goto", принимающий имя функции: `goto &NAME;`.
Однако для реализаций языков, хранящих аргументы функций и локальные переменные в стеке вызовов (что является реализацией по умолчанию для многих языков, по крайней мере, на системах с аппаратным стеком, таких как x86), реализация обобщенной оптимизации хвостовых вызовов (включая взаимную хвостовую рекурсию) представляет собой проблему: если размер кадра активации вызываемой функции отличается от размера кадра активации вызывающей функции, может потребоваться дополнительная очистка или изменение размера стекового фрейма. В таких случаях оптимизация хвостовой рекурсии остается тривиальной, но обобщенная оптимизация хвостовых вызовов может быть сложнее реализовать эффективно. Например, в виртуальной машине Java (JVM) хвостовые рекурсивные вызовы могут быть устранены (поскольку это повторно использует существующий стек вызовов), но обобщенные хвостовые вызовы – нет (поскольку это изменяет стек вызовов). В результате функциональные языки, такие как Scala, ориентированные на JVM, могут эффективно реализовывать прямую хвостовую рекурсию, но не взаимную хвостовую рекурсию. Компиляторные комплексы GCC, LLVM/Clang и Intel выполняют оптимизацию хвостовых вызовов для C и других языков на более высоких уровнях оптимизации или при передаче опции `foptimize sibling calls`. Даже если синтаксис языка явно не поддерживает эту возможность, компилятор может выполнять эту оптимизацию, если он определит, что типы возвращаемых значений вызывающей и вызываемой функций эквивалентны, а типы аргументов, передаваемых обеим функциям, либо идентичны, либо требуют одинакового объема памяти в стеке вызовов. Существуют различные методы реализации.