В информатике хвостовой вызов — это вызов подпрограммы , выполняемый как завершающее действие процедуры. [1] Если целью хвостовой рекурсии является одна и та же подпрограмма, то подпрограмма называется хвостовой рекурсией , что является частным случаем прямой рекурсии . Хвостовая рекурсия (или хвостовая рекурсия ) особенно полезна, и ее часто легко оптимизировать в реализациях.
Хвостовые вызовы могут быть реализованы без добавления нового кадра стека в стек вызовов . Большая часть фрейма текущей процедуры больше не нужна и может быть заменена фреймом хвостового вызова, соответствующим образом модифицированным (аналогично наложению для процессов, но для вызовов функций). Затем программа может перейти к вызванной подпрограмме. Создание такого кода вместо стандартной последовательности вызовов называется устранением хвостового вызова или оптимизацией хвостового вызова . Устранение хвостовых вызовов позволяет реализовать вызовы процедур в хвостовой позиции так же эффективно, как операторы goto , тем самым обеспечивая эффективное структурированное программирование . По словамГай Л. Стил , «в общем, вызовы процедур можно с пользой рассматривать как операторы GOTO, которые также передают параметры и могут быть единообразно закодированы как [машинный код] инструкции JUMP». [2]
Не все языки программирования требуют исключения хвостовых вызовов. Однако в функциональных языках программирования устранение хвостовых вызовов часто гарантируется стандартом языка , что позволяет хвостовой рекурсии использовать тот же объем памяти, что и эквивалентный цикл . Частный случай хвостовых рекурсивных вызовов, когда функция вызывает саму себя, может быть более подходящим для исключения вызовов, чем обычные хвостовые вызовы. Когда семантика языка явно не поддерживает общие хвостовые вызовы, компилятор часто все еще может оптимизировать одноуровневые вызовы или хвостовые вызовы функций, которые принимают и возвращают те же типы, что и вызывающая программа. [3]
Когда вызывается функция, компьютер должен «запомнить» место, откуда она была вызвана, обратный адрес , чтобы он мог вернуться в это место с результатом после завершения вызова. Как правило, эта информация сохраняется в стеке вызовов — простом списке местоположений возврата в порядке времени достижения описываемых ими местоположений вызовов. Для хвостовых вызовов нет необходимости запоминать вызывающего — вместо этого устранение хвостового вызова вносит только минимально необходимые изменения в фрейм стека перед его передачей [4], и функция, вызванная хвостом, вернется непосредственно к исходномуабонент. Вызов хвоста не обязательно должен лексически появляться после всех остальных операторов в исходном коде; важно только, чтобы вызывающая функция возвращалась сразу после хвостового вызова, возвращая результат хвостового вызова, если таковой имеется, поскольку вызывающая функция обходится при выполнении оптимизации.
Для нерекурсивных вызовов функций это обычно оптимизация , которая экономит лишь немного времени и места, поскольку для вызова доступно не так много разных функций. Однако при работе с рекурсивными или взаимно рекурсивными функциями, где рекурсия происходит через хвостовые вызовы, пространство стека и количество сохраненных возвратов могут стать очень значительными, поскольку функция может вызывать себя, прямо или косвенно, создавая новый кадр стека вызовов. каждый раз. Устранение хвостовых вызовов часто снижает асимптотические требования к пространству стека с линейных, или O (n), до постоянных, или O (1). Таким образом, устранение хвостовых вызовов требуется стандартными определениями некоторых языков программирования, таких как Scheme , [5][6] и языки семейства ML среди прочих. Определение языка Scheme точно формализует интуитивное понятие позиции хвоста, указывая, какие синтаксические формы позволяют иметь результаты в контексте хвоста. [7] Реализации, позволяющие неограниченному количеству хвостовых вызовов быть активными в один и тот же момент, благодаря устранению хвостовых вызовов, также можно назвать «собственно хвостовой рекурсией». [5]
Помимо пространства и эффективности выполнения, устранение хвостовых вызовов важно в идиоме функционального программирования , известной как стиль передачи продолжения (CPS), который в противном случае быстро исчерпал бы пространство стека.