7 ms·
Don't see the point really. Languages without tail recursion will perform worse. Memoization is borderline cheating, because it's a different implementation.
by rothron 8y ago
Don't see the point really.
Languages without tail recursion will perform worse. Memoization is borderline cheating, because it's a different implementation.
Fib is the poster boy for tail recursion but the reason for that is that recursion to implement fib is simply a bad choice. It's cute but that's about it. If the point is to measure function call overhead, then measure _that_?
- rothron 8y agoJust to underline the futility of this, if you are clever you can let the compiler do it. https://everything2.com/title/C%252B%252B%253A+computing+Fibonacci+numbers+at+compile+time https://everything2.com/title/C%252B%252B%253A+computing+Fib...
- eesmith 8y agoThe benchmark includes a C++ constexpr version, at https://github.com/drujensen/fib/blob/master/fib-constexpr.cpp https://github.com/drujensen/fib/blob/master/fib-constexpr.c... , with timing numbers under the section "Optimized code that breaks the benchmark" and the comment "all benchmarks will have some caveat."
- larkeith 8y agoSomewhat off topic, but I love the fact that the first post regarding compile-time Fibonacci in C++ was submitted in 2000, another user expanded on the original in 2008, and now it's being usefully referenced in 2018. I stumbled across Everything2 recently, but in many ways it strikes me as a tiny bit of the golden age of the internet, unexpectedly preserved.
- sometimesijust 8y agoIt can be a gateway for learning interesting things about the mechanics of a language, its compilation, and in turn how to make similar cases in other languages faster/cleaner/more-secure. e.g. why is nim so fast in this case? Is it tail call optimisation, not doing overflow checks, static inlining, or something else? Nim compiles to c to it is especially odd.
- fjh 8y agoWhy would languages without tail recursion optimisation perform worse when all languages use the naive implementation? It's not tail recursive, so it shouldn't make a difference, right?
- spatulon 8y agoYou're right that tail recursion doesn't help - the final operation is the addition, not a recursive call.
- DonaldPShimoda 8y ago> Fib is the poster boy for tail recursion But recursive Fibonacci isn't tail recursive. The final function call is to `+` (addition), which means that the two recursive calls must each be put on the stack and later returned so the sum can be computed. Tail recursion requires that there is no final operation other than exactly a single recursive call.
- gameswithgo 8y agosome compilers can rearrange it to be tail recursive automatically
- SeanLuke 8y agoWhich compilers can rearrange fib, with two recursive calls, into being tail recursive?
- FeepingCreature 8y agoIf it knows it's a pure function, it's possible. It'd have to be a very specific optimization pass though.
- jcranmer 8y agoAny LLVM-based compiler. GCC.
- Jtsummers 8y agoPretend you're a compiler, what changes would you make to this to make it tail recursive: fib(0) -> 1; fib(1) -> 1; fib(N) -> fib(N-1) + fib(N-2). Rules: Making a second function (fib_help) is permitted. Shouldn't use any more memory than this one uses.
- FeepingCreature 8y agoFun challenge. https://paste.pound-python.org/show/m403qNkpS5I8dnYjJGJq/ https://paste.pound-python.org/show/m403qNkpS5I8dnYjJGJq/ I wanna see the compiler that gets that.