В чем разница между хвостовыми вызовами и хвостовой рекурсией?

17

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

    
задан jjpcondor 20.08.2012 в 23:15
источник
  • Я не уверен, что понимаю этот вопрос. Разве вы уже не объяснили разницу между хвостовыми вызовами и хвостовой рекурсией? Как вы сказали, хвостовая рекурсия заключается в том, что вызов хвоста вызывает сама функция, а «хвостовой вызов» может быть вызовом любой функции. Вот в чем разница. –  sepp2k 20.08.2012 в 23:19
  • точно. en.wikipedia.org/wiki/Tail_call –  Karoly Horvath 20.08.2012 в 23:21
  • Это просто? Я подозреваю, что может быть какая-то более существенная разница, или я ошибаюсь? –  jjpcondor 20.08.2012 в 23:34
  • взаимная рекурсия также может быть хвостовой рекурсией, когда взаимно рекурсивные функции называют друг друга (а не только каждый) - всегда в хвостовой позиции. Кроме того, речь идет только о стеке. Другие ресурсы могут быть использованы или нет, что характеризует TCO - это постоянное использование стека. –  Will Ness 21.08.2012 в 11:15
  • У меня есть мечта, что когда-нибудь люди перестанут КОГДА-ЛИБО использовать термин «хвостовая рекурсия» и использовать «хвост». Концепция устранения хвостового вызова не имеет ничего общего с рекурсией. Устранение хвостового вызова проще всего реализовать для хвостовых самозанятий, но имеет смысл для любых вызовов вообще, как отметил Андреас. –  jkff 31.08.2012 в 03:10
Показать остальные комментарии

3 ответа

25

Давайте сначала устраним «хвосты».

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

Вызов в хвостовом положении может быть реализован без нажатия на что-либо в стеке, потому что старый стек кадров практически бесполезен (в предположениях, которые обычно верны на функциональных языках, но не обязательно на C и т. д.). Как сказал Гай Стил, хвостовой вызов - это прыжок, который передает аргументы.

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

Обратите внимание, что специально для обработки функций tail-recursive специально недостаточно для достижения правильной хвостовой рекурсии (особенно рекомендуется использовать хвостовой вызов any ). Терминология несколько вводит в заблуждение.

Также обратите внимание, что существуют другие способы достижения эффективности асимптотического пространства без реализации хвостовых вызовов как скачков. Например, вы можете реализовать их как обычные вызовы, а затем периодически уплотнять стек, удаляя бесполезные кадры (как-то). См. Baker's Чейни на MTA .

    
ответ дан Ryan Culpepper 21.08.2012 в 06:58
источник
  • отличный ответ! Я просто очень хотел бы, чтобы некоторые подробности о том, что именно вы имели в виду, «просто обработка хвостовых рекурсивных функций специально недостаточно для достижения правильной рекурсии хвоста». Что это значит? –  Will Ness 21.08.2012 в 11:21
  • @WillNess, см. ответ Андреаса, который рассказывает об этом и дает ссылки для более подробной информации. –  Ryan Culpepper 21.08.2012 в 16:33
  • еще одна вещь. Действительно ли старый стек кадров бесполезен? Если «tail call - это прыжок, который передает аргументы», где он передает их? В старой кадре стека, не так ли? (по крайней мере, когда он называет себя). Я думаю, что TCO - это то же самое, что повторное использование стопки кадров как прямые прыжки. В случае, скажем, трех взаимно-рекурсивных функций, три кадра могут сосуществовать и в стеке. Похоже, что TCO занимается восстановлением забытого GOTO неструктурированного программирования. :) –  Will Ness 08.09.2012 в 14:45
  • @Wall, для большинства вызовов хвоста вызывающий и вызываемый не являются одинаковыми, и, вероятно, имеют фреймы стека разного размера и макета. Возможно, вы даже не узнаете собеседника во время компиляции. Следовательно, вы не можете просто «повторно использовать кадры стека», за исключением особого случая статически известных вызовов с хвостом, т. Е. Хвостовой рекурсии (где вы скорее хотите преобразовать в цикл в любом случае). –  Andreas Rossberg 08.09.2012 в 16:29
  • Кроме того, в «чей» аргумент фрейма стека зависит от соглашения о вызове. Если вызываемый должен удалить свои аргументы из стека (как это имеет место на нескольких платформах), то вызывающий должен сделать это до хвостового вызова и перед тем, как поместить новые аргументы в стек, по крайней мере концептуально. –  Andreas Rossberg 08.09.2012 в 16:30
Показать остальные комментарии
13

Как вы говорите, хвостовая рекурсия - это особый случай хвостового вызова. Следовательно, любой язык, реализующий общую ТШО тривиально, «правильно хвост рекурсивный».

Обратное, однако, не выполняется. Существует довольно много языков, которые только оптимизируют хвостовую рекурсию, потому что это значительно проще - вы можете перевести ее прямо в цикл и не нуждаетесь в конкретной операции «хвоста», которая манипулирует стеком по-новому. Например, именно поэтому язык, компилирующий JVM, который не имеет команды хвостового вызова, как правило, только оптимизирует рекурсию хвоста (self). (Есть способы обойти отсутствие такой инструкции, например батуты, но они довольно дороги.)

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

Многие методы функционального программирования - но также и некоторые популярные шаблоны OO (см., например, ECOOP'04 Феллесина презентация или в блоге Guy Steele ) - - требуется полная полная стоимость владения (TCO).

    
ответ дан Andreas Rossberg 21.08.2012 в 12:05
источник
3

Ну, они как-то связаны друг с другом - оба они имеют в них слово «хвост», но совершенно разные ...

Рекурсия хвоста - это рекурсия с некоторыми определенными ограничениями, а вызовы хвостов - это вызовы функций. Ваш вопрос немного напоминает «в чем разница между животным и кошкой?» ...

Хвост вызова - вызов функции в положении хвоста. Примеры: f(x) в f(x) и g(★) в g(f(x)) Контрпример: f(x) в 1+f(x) и в g(f(x))

Рекурсия хвоста - это рекурсия, в которой рекурсивные вызовы являются хвостовыми вызовами. Примеры: f(★) справа от знака «=» в f(x) = f(x) , f(x,y) = if x == 0 then y else f(x-1,y+x) Я определил две рекурсивные функции, которые называют себя хвостовыми вызовами. Вот и все.

В языках с TCO хвостовые вызовы ничего не стоят, поэтому (tail) рекурсия работает в постоянном стеке, и все довольны.

    
ответ дан Axioplase 06.09.2012 в 04:01
источник