Yet another TCO thread

Also, AFAIK, Julia doesn’t implement the tail-call optimization yet, which is crucial for the performance of recursive functions.

Any recursive algorithm that tail call elimination helps can be trivially rewritten as a loop.


Tail recursion is implemented in a macro (in a package), faster for fib (but not really for scientific programming):

Moving this to a new thread as TCO discussions tend to quickly explode, and it’s irrelevant to the original discussion of Rust benchmarks (TCO cannot be used for a function like naive fib).

(As Stefan says, TCO is only for “trivial” recursion that can just as easily be written as a loop. Guaranteed TCO is mainly important in functional languages where recursion is favored over loops.)

See this thread and references therein: Does Julia have tail call optimization?


To elaborate on this: the recursive calls in the fib benchmark are not in tail position, because you add the results, so you cannot do tail call elimination (automatically or manually).


For folks interesting in unpacking this TCO-request-weary fellow’s terse statement, I recommend (at least) Chapter 1 of SICP.

As for recursive fibonacci, p. 49 in the same helps to illustrate Stefan’s later statement.