3 ms·
Yeah, I don't think this breaks any of the rules. We are still using recursion. Just leveraging what the language has to offer.
by acangiano 8y ago
Yeah, I don't think this breaks any of the rules. We are still using recursion. Just leveraging what the language has to offer.
- alangpierce 8y agoThe algorithm being benchmarked is the naive double-recursive fibonacci algorithm, which ends up performing over a billion addition operations in this case. The tail-recursive function above is the iterative bottom-up fibonacci algorithm that does it in about 50 addition operations. It's true that both use recursion, but the second is definitely not the tail-recursive version of the first. It is possible to do a form of tail call optimization for the double-recursive algorithm, described here: https://news.ycombinator.com/item?id=18096804 https://news.ycombinator.com/item?id=18096804 This reduces the number of total function calls but not the number of additions (since it's not changing the algorithm, just the way the function invocation strategy when running the algorithm).