You don't seem to have any idea how bad the exponential time taken by the naive recursive approach is.Originally Posted by Mindaugas
Therefore I will stick with microptimisations for the time being (hence the name of the thread) this means that the algorithm will be recursive.
Doubly-recursively calculating the Fib of N+1 takes more than twice the effort of calculating the Fib of N.
It's so bad that we're talking over a billion times slower to calculate even Fib(50) recursive rather than iteratively. Should you want to go to say Fib(100), it takes so long that you would literally grow old and die before it finished.
But if done using a simple loop with two variables, one can easily calculate Fib(100) in less than a millisecond.
Knowing that, I will also tell you that an iterative loop can be translated to a simple form of single-recursion, sort of the opposite of doing the tail-recursion elimination.
Tail recursion elimination is a useful skill to learn, but going the other way - not so much.
