4 ms·
The tail-recursive version of fibonacci runs just as fast as the iterative in languages with optimized tail calls. Tree- and graph traversal is often easier to
by codr7 6y ago
The tail-recursive version of fibonacci runs just as fast as the iterative in languages with optimized tail calls.
Tree- and graph traversal is often easier to reason about using recursion from my experience.
Worst case, you can get the same effect by pushing recursive calls on a stack/queue that's consumed iteratively.
- tgv 6y agoThe recursive version of Fibonacci is generally not tail recursive, but f(n) = f(n - 1) + f(n - 2).
- codr7 6y agoIt's easy enough to convert by adding arguments for the two variables used in the iterative version: https://github.com/codr7/liblg/blob/master/bench/fibiter.py https://github.com/codr7/liblg/blob/master/bench/fibiter.py https://github.com/codr7/liblg/blob/master/bench/fibtail.py https://github.com/codr7/liblg/blob/master/bench/fibtail.py
- tgv 6y agoThe point of recursion is not recursion, but a better way to write code. Better can be more readable, less errors, whatever, but adding two parameters to the Fibonacci function for the sake of introducing tail recursion, where even iteration is more understandable, is pointless.
- codr7 6y agoDepends, not all languages provide variables and since they're more or less equal it's a matter of preference in other cases.
- glandium 6y agoCode generated with tail-call optimization is, in fact, literally a loop.