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

17

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

    
задан jjpcondor 20.08.2012 в 23:15
источник

3 ответа

25

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

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

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

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

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

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

    
ответ дан Ryan Culpepper 21.08.2012 в 06:58
источник
12

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

Обратное, однако, не выполняется. Существует довольно много языков, которые только оптимизируют хвостовую рекурсию, потому что это значительно проще - вы можете перевести ее прямо в цикл и не нуждаетесь в конкретной операции «хвоста», которая манипулирует стеком по-новому. Например, именно поэтому язык, компилирующий 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
источник