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

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

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

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

Описание

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

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

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

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

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

функция   foo  (  данные  )   { 
     a  (  данные  ); 
      вернуть   б  (  данные  ); 
  } 

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

function   bar  (  данные  )   { 
     if   (  a  (  данные  ))   { 
         return   b  (  данные  ); 
      } 
     Возврат   С  (  данные  ); 
  } 

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

В этом коде:

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

функция   foo2  (  данные  )   { 
     var   ret   =   a  (  данные  ); 
      вернуть   Рет  ; 
  } 

функция   foo3  (  данные  )   { 
     var   ret   =   a  (  данные  ); 
      возврат   (  рет   ==   0  )   ?    1   :   в отставку  ; 
  } 

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

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

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

;;   факториал: число -> число 
 ;;   вычислить произведение всех положительных 
 ;;   целые числа, меньшие или равные n. 
  (  определить   (  факториал   n  ) 
  (  if   (  =   n   0  ) 
     1 
     (  *   n   (  факториал   (  -   n   1  ))))) 

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

;;   факториал: число -> число 
 ;;   вычислить произведение всех положительных 
 ;;   целые числа, меньшие или равные n. 
  (  определить   (  факториал   n  ) 
   (  факт-iter   1   n  )) 
 (  определить   (  факт-iter   произведение   n  ) 
   (  if   (  =   n   0  ) 
       произведение 
       (  факт-iter   (  *   произведение   n  ) 
                  (  -   n   1  )))) 

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

вызвать факториал (4)
    позвонить факт-итеру (1 4)
     позвонить факт-итеру (4 3)
      позвонить факт-итеру (12 2)
       позвоните факт-итеру (24 1)
       вернуть 24
      вернуть 24
     вернуть 24
    вернуть 24
   вернуть 24
 

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

вызвать факториал (4)
    позвонить факт-итеру (1 4)
    заменить аргументы на (4 3)
    заменить аргументы на (12 2)
    заменить аргументы на (24 1)
    вернуть 24
   вернуть 24
 

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

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

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

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

Пример кода

% Пролог, хвостовая рекурсия по модулю минусы: раздел ([], _ , [], []). раздел ([ X | Xs ], Pivot , [ X | Rest ], Bigs ) : - X @< Pivot , !, раздел ( Xs , Pivot , Rest , Bigs ). раздел ([ X | Xs ], Pivot , Смоллс , [ X | Rest ]) : - раздел ( Xs , Pivot , Смоллс , Rest ).	-- В Haskell защищенная рекурсия: раздел [] _ ​​= ( [] , [] ) раздел ( x : xs ) p | Икс < п знак равно ( Икс : а , б ) | иначе = ( a , x : b ) где ( a , b ) = раздел xs p
% Пролог с явными унификациями: % нехвостовая рекурсия перевода: раздел ([], _ , [], []). раздел ( L , Поворот , Смоллс , Бигс ) :- L = [ X | Xs ], ( X @< Pivot -> раздел ( Xs , Pivot , Rest , Bigs ), Smalls = [ X | Rest ] ; раздел ( Xs , Pivot , Smalls , Rest ), Bigs = [ X | Rest ] ).	% Пролог с явными унификациями: % хвостовая рекурсия перевода: раздел ([], _ , [], []). раздел ( L , Поворот , Смоллс , Бигс ) :- L = [ X | Xs ], ( X @< Pivot -> Smalls = [ X | Rest ], раздел ( Xs , Pivot , Rest , Bigs ) ; Bigs = [ X | Rest ], раздел ( Xs , Pivot , Smalls , Rest ) ).

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

Пример C

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

typedef структур список { void * value ; структур список * следующий ; } список ; список * дубликат ( const list * ls ) { список * head = NULL ; if ( ls != NULL ) { list * p = дубликат ( ls -> next ); голова = malloc ( sizeof * head ); голова -> значение = ls -> значение ; голова -> следующий = р ; } вернуть голову ; }	;; в схеме, ( define ( dубликат ls ) ( if ( not ( null? ls )) ( cons ( car ls ) ( дубликат ( cdr ls ))) ' ()))
	%% в Прологе, дубликат ([ X | Xs ], R ): - дубликат ( Xs , Ys ), R = [ X | Да ]. дубликат ([],[]).

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

typedef структур список { void * value ; структур список * следующий ; } список ; void дубликат_aux ( const list * ls , list * end ); список * дубликат ( const list * ls ) { списка заголовок ; дубликат_aux ( ls и голова ; ) вернуть голову . следующий ; } void дубликат_aux ( const list * ls , list * end ) { if ( ls != NULL ) { end -> next = malloc ( sizeof * end ); конец -> следующий -> значение = ls -> значение ; дубликат_aux ( ls -> следующий , конец -> следующий ); } Еще { конец -> следующий = NULL ; } }

;; в схеме, ( define ( дублировать ls ) ( let (( head ( list 1 ))) ( let dup (( ls ls ) ( end head )) ( cond (( not ( null? ls )) ( set-cdr! end ( список ( car ls ))) ( dup ( cdr ls ) ( cdr end ))))) ( cdr head )))

%% в Прологе, дубликат ([ X | Xs ], R ):- R = [ X | Ys ], дубликат ( Xs , Ys ). дубликат ([],[]).

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

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

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

typedef структур список { void * value ; структур список * следующий ; } список ; список * дубликат ( const list * ls ) { списка заголовок , * конец ; конец = & голова ; while ( ls != NULL ) { end -> next = malloc ( sizeof * end ); конец -> следующий -> значение = ls -> значение ; ls = ls -> следующий ; конец = конец -> следующий ; } Конец -> следующий = NULL ; вернуть голову . следующий ; }	;; в схеме, ( define ( дубликат ls ) ( let (( head ( list 1 ))) ( do (( end head ( cdr end )) ( ls ls ( cdr ls ))) (( null? ls ) ( cdr head ) ) ( set-cdr! end ( список ( car ls ))))))
	%% в Прологе, %% Н/Д

История

В докладе, представленном на конференции 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: 
   вызов   B 
   вызов   A 
   ret 

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

 foo: 
   позвонить   B 
   jmp    A 

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

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

функция  foo(данные1, данные2) 
     Б(данные1) 
     вернуть  А (данные2) 
 

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

 foo: 
    mov    reg  , [  sp  +  data1  ]   ;   извлечь данные1 из параметра стека (sp) в рабочий регистр. 
     нажать   рег              ;   поместить data1 в стек, где B ожидает 
    вызова   B                ;   B использует data1 
    pop                   ;   удалить данные1 из стека 
    mov    reg  ,[  sp  +  data2  ]   ;   извлечь данные2 из параметра стека (sp) в рабочий регистр. 
     нажать   рег              ;   поместить data2 в стек, где A ожидает 
    вызова   A                ;   A использует data2 
    pop                   ;   удалить данные2 из стека. 
     в отставку 

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

 foo: 
    mov    reg  , [  sp  +  data1  ]   ;   извлечь данные1 из параметра стека (sp) в рабочий регистр. 
     нажать   рег              ;   поместить data1 в стек, где B ожидает 
    вызова   B                ;   B использует data1 
    pop                   ;   удалить данные1 из стека 
    mov    reg  ,[  sp  +  data2  ]   ;   извлечь данные2 из параметра стека (sp) в рабочий регистр. 
     mov    [  sp  +  data1  ],  reg   ;   поместите данные2 туда, где A ожидает их 
    jmp    A                ;   A использует data2 и немедленно возвращает вызывающему абоненту. 

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

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

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

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

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

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

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

процедура  foo(  x  ) 
      если   п  (  х  ) 
          возвратный  бар(  x  ) 
      иначе 
         верните  foo(baz(  x  )) 
 

в

процедура  foo(  x  ) 
      хотя   верно 
         , если   p  (  x  ) 
              возвратный  бар(  x  ) 
          иначе 
             x  ← baz(  x  ) 
 

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

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

процедура  foo(  x  ) 
      если   п  (  х  ) 
          возвратный  бар(  x  ) 
      иначе, если   q  (  x  ) 
          вернуть  баз(  х  ) 
      ... 
      иначе, если   р  (  х  ) 
          вернуть  foo(qux(  x  )) 
      ... 
      иначе 
         верните  foo(quux(  x  )) 
 

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

процедура  foo(  x  ) 
      хотя   верно 
         , если   p  (  x  ) 
              возвратный  бар(  x  ) 
          иначе, если   q  (  x  ) 
              вернуть  баз(  х  ) 
          ... 
          иначе, если   р  (  х  ) 
              х  ← qux(  x  ) 
          ... 
          иначе 
             x  ← quux(  x  ) 
 

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

функция   факториал  (  n  ), 
     если   n   ==   0, 
         возвращает   1 
     , иначе 
         возвращает   n   *   факториал  (  n   -   1  ) 
     end 
 end 

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

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

функция   факториал  (  n  ::  Integer  ,   a  ::  Integer  ) 
     , если   n   ==   0  : 
         вернуть   a 
     else 
         вернуть   факториал  (  n   -   1  ,   n   *   a  ) 
     end 
 end 

 function   Factorial  (  n  ::  Integer  ) 
     вернуть   факториал  (  n  ,   1  ) 
 конец 

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

функция   fact_iter  (  n  ::  Integer  ,   a  ::  Integer  ) 
     while   n   >   0 
         a   =   n   *   a 
         n   =   n   -   1 
     end 
     возвращает   конечный 
 функции 

 факториал   fact_iter  (  n  ::  Integer  ) 
     return   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 есть команда хвостового вызова.
• Зиг – Да

См. также

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