Computing Fibonacci numbers iteratively is only slightly less absurd. It's `O(n)` for what should be an `O(log(n))` problem (`fib(n) = round ((phi^n - phi^-n)/(2phi-1))`).
Eh, by recursion I meant specifically the exponential "fib(n - 1) + fib(n - 2)" flavored definition. If you're writing the linear-time algorithm and happen to do the iteration via tail recursion, I don't think there's anything absurd about that
Comments
Is it really absurd? If the compiler can turn it into iteration, then it's a big boy compiler. If not, then meh?
Computing Fibonacci numbers iteratively is only slightly less absurd. It's `O(n)` for what should be an `O(log(n))` problem (`fib(n) = round ((phi^n - phi^-n)/(2phi-1))`).
Ay, yes, I was focused on the idea that I want my compilers to do TCO and other optimizations, so I missed the point.
Eh, by recursion I meant specifically the exponential "fib(n - 1) + fib(n - 2)" flavored definition. If you're writing the linear-time algorithm and happen to do the iteration via tail recursion, I don't think there's anything absurd about that