Ограничение глубины рекурсии в хвостовой рекурсии на языках, реализующих TCO?

Question

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

Я предполагаю, что теоретический предел НЕТ, так как нет рекурсивного процесса, хотя это рекурсивная процедура. Практическим ограничением будет то, что доступная основная память может быть использована. Пожалуйста, уточните или исправьте, если я где-то ошибаюсь.

Answer 1

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

Подводя итог, нет практического предела.

Answer 2

В дополнение к тому, что написал @Mehrdad Afshari, я просто хочу указать, что на самом деле очень важно, чтобы хвостовая рекурсия (или, скорее, цепочка хвостовых вызовов) могла быть потенциально бесконечной, потому что иначе вы не могли бы написать веб-сервер, операционная система, интерпретатор, REPL или действительно какой-либо цикл обработки событий на функциональном языке.

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

В принципе, это то, как вы пишете веб-сервер на функциональном языке:

def loop(queue) = { 
    // handle first request in queue 
    loop(queue) 
} 

Без бесконечной рекурсии хвоста, это будет быстро запустить из памяти.