Я понимаю, что хвостовая рекурсия - это особый случай, когда функция делает хвостовые вызовы для себя. Но я не понимаю, как хвосты и хвостовая рекурсия различны. В "правильном хвостовом рекурсивном" языке с реализованной TCO (оптимизация хвостового вызова), как и схема, это означает, что хвостовые и хвостовые рекурсии не потребляют стек или другие ресурсы. В языке, на котором компилятор не может оптимизировать хвостовую рекурсию, программа может закончиться стеком и сбой. В "правильных хвостовых рекурсивных" языках реализация хвостовой рекурсии для цикла не менее эффективна, чем использование цикла, я полагаю.
В чем разница между хвостовыми вызовами и хвостовой рекурсией?
Ответ 1
Сначала устраните "хвостовые вызовы".
Вызов в хвостовом положении - это вызов функции, результат которого немедленно возвращается как значение функции включения. Положение хвоста является статическим свойством.
Вызов в хвостовом положении может быть реализован без нажатия на что-либо в стеке, потому что старый стек кадров практически бесполезен (в предположениях, которые обычно верны на функциональных языках, но не обязательно на C и т.д.). Как сказал Гай Стил, хвостовой вызов - это прыжок, который передает аргументы.
Грубо говоря, реализация языка корректно рекурсивно хвоста, если она имеет такое же использование асимптотического пространства, как и для всех вызовов в хвостовом положении как скачки без роста стека. Это действительно грубое упрощение. Если вам нужна полная история, см. Clinger Правильная рекурсия хвоста и эффективность использования пространства.
Обратите внимание, что специально для обработки хвостовых рекурсивных функций недостаточно для обеспечения правильной рекурсии хвоста (любой хвостовой вызов должен быть специально обработан). Терминология несколько вводит в заблуждение.
Также обратите внимание, что существуют другие способы достижения эффективности асимптотического пространства без реализации хвостовых вызовов как скачков. Например, вы можете реализовать их как обычные вызовы, а затем периодически уплотнять стек, удаляя бесполезные кадры (как-то). См. Baker Чейни на MTA.
Ответ 2
Как вы говорите, хвостовая рекурсия - это особый случай хвостового вызова. Следовательно, любой язык, реализующий общую ТШО тривиально, "правильно хвост рекурсивный".
Обратное, однако, не выполняется. Существует довольно много языков, которые только оптимизируют хвостовую рекурсию, потому что это значительно проще - вы можете перевести ее прямо в цикл и не нуждаетесь в конкретной операции "хвоста", которая манипулирует стеком по-новому. Например, именно поэтому язык, компилирующий JVM, который не имеет команды хвостового вызова, как правило, только оптимизирует рекурсию хвоста (self). (Есть способы обойти отсутствие такой инструкции, например батуты, но они довольно дороги.)
Оптимизация полного хвостового вызова применяется не только к саморегуляционным (или взаимно) рекурсивным вызовам, но и к любым вызовам в позиции хвоста. В частности, он распространяется на вызовы, чья цель не статически известна, например. при вызове функции первого класса или динамически-отправленного метода! Следовательно, для этого требуются несколько более сложные (хотя и известные) методы реализации.
Многие методы функционального программирования - но также и некоторые популярные шаблоны OO (см. например презентация Felleisen ECOOP'04 или Сообщение в блоге Guy Steele) - требуется полная полная стоимость владения TCO.
Ответ 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) рекурсия работает в постоянном стеке, и все довольны.