Хвостовой вызов

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

Хвостовые вызовы могут быть реализованы без добавления нового кадра стека в стек вызовов . Большая часть кадра текущей процедуры больше не нужна и может быть заменена кадром хвостового вызова, измененным соответствующим образом (аналогично наложению для процессов, но для вызовов функций). Затем программа может перейти к вызванной подпрограмме. Создание такого кода вместо стандартной последовательности вызовов называется устранением хвостового вызова или оптимизацией хвостового вызова . Устранение хвостового вызова позволяет реализовывать вызовы процедур в хвостовой позиции так же эффективно, как операторы перехода , что позволяет эффективно структурировать программирование . По словам Гая Л. Стила , «в общем, вызовы процедур можно с пользой рассматривать как операторы GOTO, которые также передают параметры, и могут быть единообразно закодированы как инструкции [машинного кода] JUMP».

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

Описание

Когда вызывается функция, компьютер должен «запомнить» место, из которого она была вызвана, адрес возврата , чтобы он мог вернуться в это место с результатом после завершения вызова. Обычно эта информация сохраняется в стеке вызовов — списке мест возврата в том порядке, в котором были достигнуты места вызова. Для хвостовых вызовов нет необходимости запоминать вызывающую сторону — вместо этого устранение хвостовых вызовов вносит только минимально необходимые изменения в кадр стека перед его передачей. и функция, вызываемая хвостом, вернется непосредственно к исходному вызывающему объекту. Хвостовой вызов не обязательно должен стоять лексически после всех остальных операторов исходного кода; важно только, чтобы вызывающая функция возвращалась сразу после хвостового вызова, возвращая результат хвостового вызова, если таковой имеется, поскольку вызывающая функция обходится при выполнении оптимизации.

Для нерекурсивных вызовов функций обычно это оптимизация , которая экономит лишь немного времени и места, поскольку различных функций, доступных для вызова, не так уж и много. Однако при работе с рекурсивными или взаимно рекурсивными функциями, где рекурсия происходит посредством хвостовых вызовов, пространство стека и количество сохраненных возвратов могут стать очень значительными, поскольку функция может вызывать себя прямо или косвенно, создавая новый кадр стека вызовов. каждый раз. Устранение хвостового вызова часто снижает асимптотические требования к пространству стека с линейного, или O (n), до постоянного, или O (1). Таким образом, исключение хвостовых вызовов требуется стандартными определениями некоторых языков программирования, таких как Scheme , и языки семейства ML среди других. Определение языка Scheme точно формализует интуитивное понятие положения хвоста, определяя, какие синтаксические формы позволяют получать результаты в контексте хвоста. Реализации, позволяющие одновременно активировать неограниченное количество хвостовых вызовов, благодаря устранению хвостовых вызовов, также можно назвать «правильно хвостовой рекурсией».

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

Синтаксическая форма

Хвостовой вызов может располагаться непосредственно перед синтаксическим концом функции:

function foo(data) {
    a(data);
    return b(data);
}

Здесь оба a(data) и b(data) это звонки, но b это последнее, что процедура выполняет перед возвратом и, таким образом, находится в хвостовой позиции. Однако не все хвостовые вызовы обязательно расположены в синтаксическом конце подпрограммы:

function bar(data) {
    if (a(data)) {
        return b(data);
    }
    return c(data);
}

Здесь оба вызова b и c находятся в хвостовом положении. Это связано с тем, что каждый из них находится в конце if-ветви соответственно, хотя первый синтаксически не находится в конце ветки if. barтело.

В этом коде:

function foo1(data) {
    return a(data) + 1;
}

function foo2(data) {
    var ret = a(data);
    return ret;
}

function foo3(data) {
    var ret = a(data);
    return (ret == 0) ? 1 : ret;
}

звонок в a(data) находится в положении хвоста в foo2, но он не находится в хвостовом положении ни в foo1 или в foo3, поскольку управление должно вернуться к вызывающему объекту, чтобы он мог проверить или изменить возвращаемое значение перед его возвратом.

Примеры программ

Следующая программа является примером в Scheme :

;; factorial : number -> number
;; to calculate the product of all positive
;; integers less than or equal to n.
(define (factorial n)
 (if (= n 0)
    1
    (* n (factorial (- n 1)))))

Это не написано в стиле хвостовой рекурсии, поскольку функция умножения ("*") находится в хвостовой позиции. Это можно сравнить с:

;; factorial : number -> number
;; to calculate the product of all positive
;; integers less than or equal to n.
(define (factorial n)
  (fact-iter 1 n))
(define (fact-iter product n)
  (if (= n 0)
      product
      (fact-iter (* product n)
                 (- n 1))))

Эта программа предполагает оценку аппликативного порядка . Внутренняя процедура fact-iter вызывает себя последним в потоке управления. Это позволяет интерпретатору или компилятору реорганизовать выполнение, которое обычно выглядит так:

  call factorial (4)
   call fact-iter (1 4)
    call fact-iter (4 3)
     call fact-iter (12 2)
      call fact-iter (24 1)
      return 24
     return 24
    return 24
   return 24
  return 24

в более эффективный вариант как с точки зрения пространства, так и с точки зрения времени:

  call factorial (4)
   call fact-iter (1 4)
   replace arguments with (4 3)
   replace arguments with (12 2)
   replace arguments with (24 1)
   return 24
  return 24

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

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

Хвостовая рекурсия по модулю минусов

Хвостовая рекурсия по модулю cons - это обобщение оптимизации хвостовой рекурсии, представленной Дэвидом Х. Д. Уорреном. в контексте компиляции Пролога явно рассматривается как заданный язык . Он был описан (хотя и не назван) Дэниелом П. Фридманом и Дэвидом С. Уайзом в 1974 году. как метод компиляции LISP . Как следует из названия, он применяется, когда единственная операция, которую остается выполнить после рекурсивного вызова, — это добавить известное значение перед возвращаемым из него списком (или вообще выполнить постоянное количество простых операций по созданию данных). Таким образом, этот вызов будет хвостовым вызовом, за исключением (« по модулю ») указанной операции cons . Но добавление значения в начало списка при выходе из рекурсивного вызова — это то же самое, что добавление этого значения в конец растущего списка при входе в рекурсивный вызов, таким образом создавая список как побочный эффект , как если бы в неявный параметр аккумулятора. Следующий фрагмент Пролога иллюстрирует эту концепцию:

Пример кода

% Prolog, tail recursive modulo cons: partition([], _, [], []). partition([X|Xs], Pivot, [X|Rest], Bigs) :- X @< Pivot, !, partition(Xs, Pivot, Rest, Bigs). partition([X|Xs], Pivot, Smalls, [X|Rest]) :- partition(Xs, Pivot, Smalls, Rest).	-- In Haskell, guarded recursion: partition [] _ = ([],[]) partition (x:xs) p | x < p = (x:a,b) | otherwise = (a,x:b) where (a,b) = partition xs p
% Prolog, with explicit unifications: % non-tail recursive translation: partition([], _, [], []). partition(L, Pivot, Smalls, Bigs) :- L=[X|Xs], ( X @< Pivot -> partition(Xs,Pivot,Rest,Bigs), Smalls=[X|Rest] ; partition(Xs,Pivot,Smalls,Rest), Bigs=[X|Rest] ).	% Prolog, with explicit unifications: % tail-recursive translation: partition([], _, [], []). partition(L, Pivot, Smalls, Bigs) :- L=[X|Xs], ( X @< Pivot -> Smalls=[X|Rest], partition(Xs,Pivot,Rest,Bigs) ; Bigs=[X|Rest], partition(Xs,Pivot,Smalls,Rest) ).

Таким образом, при хвостовой рекурсии такой вызов преобразуется в создание нового узла списка и установку его first поле, а затем выполнить хвостовой вызов с указателем на узел rest поле в качестве аргумента, которое будет заполняться рекурсивно. Тот же эффект достигается, когда рекурсия защищена лениво вычисляемым конструктором данных, что автоматически достигается в ленивых языках программирования, таких как Haskell.

Пример С

Следующий фрагмент определяет рекурсивную функцию на C , которая дублирует связанный список (с некоторым эквивалентным кодом Scheme и Prolog в качестве комментариев для сравнения):

typedef struct list { void *value; struct list *next; } list; list *duplicate(const list *ls) { list *head = NULL; if (ls != NULL) { list *p = duplicate(ls->next); head = malloc(sizeof *head); head->value = ls->value; head->next = p; } return head; }	;; in Scheme, (define (duplicate ls) (if (not (null? ls)) (cons (car ls) (duplicate (cdr ls))) '()))
	%% in Prolog, duplicate([X|Xs],R):- duplicate(Xs,Ys), R=[X|Ys]. duplicate([],[]).

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

typedef struct list { void *value; struct list *next; } list; void duplicate_aux(const list *ls, list *end); list *duplicate(const list *ls) { list head; duplicate_aux(ls, &head); return head.next; } void duplicate_aux(const list *ls, list *end) { if (ls != NULL) { end->next = malloc(sizeof *end); end->next->value = ls->value; duplicate_aux(ls->next, end->next); } else { end->next = NULL; } }	;; in Scheme, (define (duplicate ls) (let ((head (list 1))) (let dup ((ls ls) (end head)) (cond ((not (null? ls)) (set-cdr! end (list (car ls))) (dup (cdr ls) (cdr end))))) (cdr head)))
	%% in Prolog, duplicate([X|Xs],R):- R=[X|Ys], duplicate(Xs,Ys). duplicate([],[]).

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

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

Реализация хвостовой рекурсии теперь может быть преобразована в явно итеративную реализацию в виде накопительного цикла :

typedef struct list { void *value; struct list *next; } list; list *duplicate(const list *ls) { list head, *end; end = &head; while (ls != NULL) { end->next = malloc(sizeof *end); end->next->value = ls->value; ls = ls->next; end = end->next; } end->next = NULL; return head.next; }	;; in Scheme, (define (duplicate ls) (let ((head (list 1))) (do ((end head (cdr end)) (ls ls (cdr ls ))) ((null? ls) (cdr head)) (set-cdr! end (list (car ls))))))
	%% in Prolog, %% N/A

История

В докладе, представленном на конференции ACM в Сиэтле в 1977 году, Гай Л. Стил подвел итог дебатам по поводу GOTO и структурированного программирования и заметил, что вызовы процедур в хвостовой позиции процедуры лучше всего рассматривать как прямую передачу управления вызываемая процедура, обычно исключающая ненужные операции манипуляции стеком. Поскольку такие «хвостовые вызовы» очень распространены в Lisp , языке, где вызовы процедур встречаются повсеместно, эта форма оптимизации значительно снижает стоимость вызова процедуры по сравнению с другими реализациями. Стил утверждал, что плохо реализованные вызовы процедур привели к искусственному восприятию того, что GOTO дешевле по сравнению с вызовом процедур. Стил далее утверждал, что «в целом вызовы процедур можно с пользой рассматривать как операторы GOTO, которые также передают параметры, и могут быть единообразно закодированы как инструкции [машинного кода] JUMP», при этом инструкции по манипуляции стеком машинного кода «считаются оптимизацией (а не наоборот!)". Стил привел доказательства того, что хорошо оптимизированные численные алгоритмы на Lisp могут выполняться быстрее, чем код, созданный доступными на тот момент коммерческими компиляторами Fortran, поскольку стоимость вызова процедуры в Lisp была намного ниже. В Scheme , диалекте Лиспа, разработанном Стилом совместно с Джеральдом Джеем Суссманом , исключение хвостовых вызовов гарантированно будет реализовано в любом интерпретаторе.

Методы реализации

Хвостовая рекурсия важна для некоторых языков высокого уровня , особенно функциональных и логических языков, а также членов семейства Lisp . В этих языках хвостовая рекурсия является наиболее часто используемым (а иногда и единственным доступным способом) способа реализации итерации. Спецификация языка Scheme требует, чтобы хвостовые вызовы были оптимизированы, чтобы не увеличивать стек. Хвостовые вызовы в Perl могут быть выполнены явно с помощью варианта оператора goto, который принимает имя функции: goto &NAME;

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

Например, в виртуальной машине Java (JVM) вызовы хвостовой рекурсии можно исключить (поскольку при этом повторно используется существующий стек вызовов), но нельзя исключить общие хвостовые вызовы (поскольку это изменяет стек вызовов). В результате функциональные языки, такие как Scala , ориентированные на JVM, могут эффективно реализовать прямую хвостовую рекурсию, но не взаимную хвостовую рекурсию.

Комплекты компиляторов GCC и , LLVM/Clang Intel выполняют хвостовую оптимизацию для C и других языков на более высоких уровнях оптимизации или когда -foptimize-sibling-calls вариант пройден. Хотя данный синтаксис языка может не поддерживать это явно, компилятор может выполнить эту оптимизацию всякий раз, когда он может определить, что типы возвращаемых значений для вызывающего и вызываемого объекта эквивалентны и что типы аргументов, передаваемых в обе функции, либо одинаковы, либо требуют тот же объем общего пространства в стеке вызовов.

Доступны различные методы реализации.

В сборе

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

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

 foo:
  call B
  call A
  ret

При исключении хвостового вызова последние две строки заменяются одной инструкцией перехода:

 foo:
  call B
  jmp  A

После подпрограммы A завершается, он возвращается непосредственно на обратный адрес foo, опуская ненужное ret заявление.

Обычно вызываемые подпрограммы должны быть снабжены параметрами . Таким образом, сгенерированный код должен убедиться, что кадр вызова для A правильно настроен, прежде чем переходить к подпрограмме, вызываемой хвостом. Например, на платформах , где стек вызовов содержит не только адрес возврата , но и параметры подпрограммы, компилятору может потребоваться выдать инструкции для настройки стека вызовов. На такой платформе для кода:

function foo(data1, data2)
   B(data1)
   return A(data2)

(где data1 и data2 являются параметрами), компилятор мог бы перевести это как:

 foo:
   mov  reg,[sp+data1] ; fetch data1 from stack (sp) parameter into a scratch register.
   push reg            ; put data1 on stack where B expects it
   call B              ; B uses data1
   pop                 ; remove data1 from stack
   mov  reg,[sp+data2] ; fetch data2 from stack (sp) parameter into a scratch register.
   push reg            ; put data2 on stack where A expects it
   call A              ; A uses data2
   pop                 ; remove data2 from stack.
   ret

Оптимизатор хвостового вызова может затем изменить код на:

 foo:
   mov  reg,[sp+data1] ; fetch data1 from stack (sp) parameter into a scratch register.
   push reg            ; put data1 on stack where B expects it
   call B              ; B uses data1
   pop                 ; remove data1 from stack
   mov  reg,[sp+data2] ; fetch data2 from stack (sp) parameter into a scratch register.
   mov  [sp+data1],reg ; put data2 where A expects it
   jmp  A              ; A uses data2 and returns immediately to caller.

Этот код более эффективен как с точки зрения скорости выполнения, так и с точки зрения использования пространства стека.

Через прыжки на батуте

Поскольку многие компиляторы Scheme используют C в качестве промежуточного целевого кода, хвостовую рекурсию необходимо кодировать на C без увеличения стека, даже если компилятор C не оптимизирует хвостовые вызовы. Во многих реализациях это достигается за счет использования устройства, известного как батут — фрагмента кода, который неоднократно вызывает функции. Все функции вводятся через батут. Когда функция должна выполнить хвостовой вызов другой, вместо того, чтобы вызывать ее напрямую и затем возвращать результат, она возвращает адрес вызываемой функции и параметры вызова обратно в батут (из которого она была вызвана), а Trumpoline позаботится о следующем вызове этой функции с указанными параметрами. Это гарантирует, что стек C не будет расти и итерация может продолжаться бесконечно.

Реализовать батуты можно с помощью функций высшего порядка в языках, которые их поддерживают, таких как Groovy , Visual Basic .NET и C# .

Использование батута для всех вызовов функций обходится гораздо дороже, чем обычный вызов функции C, поэтому по крайней мере один компилятор Scheme, Chicken , использует технику, впервые описанную Генри Бейкером из неопубликованного предложения Эндрю Аппеля . в котором используются обычные вызовы C, но размер стека проверяется перед каждым вызовом. Когда стек достигает максимально допустимого размера, объекты в стеке удаляются с помощью алгоритма Чейни, перемещая все текущие данные в отдельную кучу. После этого стек разматывается («выталкивается»), и программа возобновляет работу из состояния, сохраненного непосредственно перед сборкой мусора. Бейкер говорит: «Метод Аппеля позволяет избежать большого количества небольших прыжков на батуте, время от времени спрыгивая с Эмпайр-стейт-билдинг». Сбор мусора гарантирует, что взаимная хвостовая рекурсия может продолжаться бесконечно. Однако этот подход требует, чтобы ни один вызов функции C никогда не возвращался, поскольку нет гарантии, что кадр стека ее вызывающей стороны все еще существует; следовательно, он предполагает гораздо более радикальное внутреннее переписывание программного кода: стиль передачи продолжения .

Связь с while оператором

Хвостовая рекурсия может быть связана с while оператором , явной итерацией, например, путем преобразования

procedure foo(x)
    if p(x)
        return bar(x)
    else
        return foo(baz(x))

в

procedure foo(x)
    while true
        if p(x)
            return bar(x)
        else
            x ← baz(x)

где x может быть кортежем, включающим более одной переменной: в этом случае необходимо соблюдать осторожность при реализации оператора присваивания x ← baz( x ), чтобы соблюдались зависимости. Возможно, потребуется ввести вспомогательные переменные или использовать конструкцию подкачки .

В более общем смысле,

procedure foo(x)
    if p(x)
        return bar(x)
    else if q(x)
        return baz(x)
    ...
    else if r(x)
        return foo(qux(x))
    ...
    else
        return foo(quux(x))

может быть преобразован в

procedure foo(x)
    while true
        if p(x)
            return bar(x)
        else if q(x)
            return baz(x)
        ...
        else if r(x)
            x ← qux(x)
        ...
        else
            x ← quux(x)

Например, эта программа Julia дает определение без хвостовой рекурсии. fact факториала:

function factorial(n)
    if n == 0
        return 1
    else
        return n * factorial(n - 1)
    end
end

Действительно, n * factorial(n - 1) завершает вызов factorial. Но его можно преобразовать в определение хвостовой рекурсии, добавив аргумент a называется аккумулятором .

Эта программа Julia дает определение хвостовой рекурсии. fact_iter факториала:

function factorial(n::Integer, a::Integer)
    if n == 0:
        return a
    else
        return factorial(n - 1, n * a)
    end
end

function factorial(n::Integer)
    return factorial(n, 1)
end

Эта программа Джулии дает итеративное определение fact_iter факториала:

function fact_iter(n::Integer, a::Integer)
    while n > 0
        a = n * a
        n = n - 1
    end
    return a
end

function factorial(n::Integer)
    return fact_iter(n, one(n))
end

Языковая поддержка

• Clojure – у Clojure есть recur особая форма.
• Common Lisp — некоторые реализации выполняют оптимизацию хвостового вызова во время компиляции, если оптимизируют скорость.
• Эликсир – Эликсир реализует оптимизацию хвостового вызова, как и все языки, которые в настоящее время ориентированы на виртуальную машину BEAM.
• Вяз – Да
• Эрланг – Да
• F# – F# по умолчанию реализует совокупную стоимость владения, где это возможно.
• Перейти – нет поддержки
• Хаскель – да
• JavaScript — механизмы, совместимые с ECMAScript 6.0, должны иметь хвостовые вызовы. который теперь реализован в Safari / WebKit но отклонен V8 и SpiderMonkey
• Котлин – Имеет tailrec модификатор для функций
• Lua – хвостовая рекурсия требуется по определению языка.
• Objective-C — компилятор оптимизирует хвостовые вызовы, если указана опция -O1 (или выше), но ее легко нарушить вызовами, добавленными автоматическим подсчетом ссылок (ARC).
• ОКамл – Да
• Perl – явный вариант оператора goto, который принимает имя функции: goto &NAME;
• Чистый скрипт – Да
• Python — стандартные реализации Python не выполняют оптимизацию хвостового вызова, хотя для этого доступен сторонний модуль. Изобретатель языка Гвидо ван Россум утверждает, что трассировки стека изменяются в результате исключения хвостовых вызовов, что усложняет отладку, и предпочитает, чтобы программисты вместо этого использовали явную итерацию . По этой причине ожидается, что Python никогда не будет реализовывать оптимизацию хвостовых вызовов.
• R – Да, функция Tailcall() появилась в R.4.4.0.
• Ракетка – Да
• Ruby – Да, но отключен по умолчанию.
• Rust — оптимизацию хвостового вызова можно выполнить в ограниченных случаях, но это не гарантируется.
• Scala — функции хвостовой рекурсии автоматически оптимизируются компилятором. Такие функции также могут быть дополнительно отмечены значком @tailrec аннотация, которая делает ошибку компиляции, если функция не является хвостовой рекурсивной
• Схема – требуется определением языка.
• Swift — в некоторых случаях (по состоянию на 2014 год).
• Tcl – начиная с Tcl 8.6, в Tcl есть команда хвостового вызова.
• Зиг – Да

См. также

• Рекурсия курса значений
• Рекурсия (информатика)
• Примитивная рекурсивная функция
• Встроенное расширение
• Листовая подпрограмма
• Корекурсия