Limit depth of recursion in tail recursion in languages implementing TCO?
What is the theoretical / practical limit for recursion depth in languages implementing Tail Call optimization? (Please assume that the repeating function is correctly called tail.)
I assume the theoretical limit is NONE since there is no recursive process, although it is a recursive procedure. A practical limitation will be that the available main memory can be used. Please clarify or correct if I am wrong somewhere.
When the tail recursive function is optimized, it will essentially become an iterative function. The compiler reuses the original call's stack frame for subsequent calls, so you won't have any free space. If you don't allocate any heap memory (or any other kind of memory that isn't on the stack, for that matter) , you can have infinitely deep (if you're patient enough;)) recursion (think of it as an infinite loop , it has the same characteristics).
To summarize, there is no practical limit.
a source to share
In addition to what @Mehrdad Afshari wrote, I just want to point out that it is actually very important that tail recursion (or rather a chain of tail calls) could be potentially infinite, since otherwise you could not write the web -server, operating system, interpreter, REPL, or really any kind of event loop in functional language.
After all, the operating system is nothing more than an infinite loop, and the way to write a loop in functional language is by using tail recursion. If the tail recursion was not infinite, the loop would not be infinite. Therefore, you could not only not write an operating system, but the language would not be complete either.
Basically, this is how you write a web server in a functional language:
def loop(queue) = {
// handle first request in queue
loop(queue)
}
Without endless tail recursion, this will end quickly.
a source to share