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.

7 Likes

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?

5 Likes

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).

4 Likes

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.

3 Likes