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.
9 Likes
Tail recursion is implemented in a macro (in a package), faster for fib (but not really for scientific programming):
https://github.com/JuliaLang/julia/issues/4964#issuecomment-955560668
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.
4 Likes