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

Question

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

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

Answer 1

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

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

Answer 2

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

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

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

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

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