implementations of the fib function explained and analysed (memoization/recursion explained)
Here are 3 implementations of the fibonacci function explained
the iterative solution is probably what comes to mind first.
say n = 5, we can observe
Recursion and memoization:
Firstly, a definition of memoization that i copy pasted:
- In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
this works in the same way as the recursive approach, except it adds to it with memoization;
this approach distinguishes between already calculated numbers and not calculated numbers in a dictionary (
cache) so you never recalculate the same numbers.
However, this approach comes with a drawback in the form of taking up more memory.
(Note: i did not make these findings myself)
The complexity of the iterative Fibonacci series is considered to be liner O(n), but the problem comes when is N is large enough, so generally it will not be linear.
Recursive T(n) = O(1.6180)^n
Memoization T(n) = n
- in python recursion is less efficient to iteration however some other languages act differently
P.S repost because i accidentally put it on the share board before so i took that post down.
check this post to see my implementation of the recursive fib func with memoization in one line :)
I noticed that for your iterative version you were storing intermediate results; but that takes time to manipulate the list. Since we need only the last two values, we can do away with the list altogether. I implemented another version called
fib_const_space that is also iterative and goes a little faster than your original iterative version.
Sorry, I'm new to Repl.it and I was just poking around. When I forked your code, I thought that there might have been a way for you to see it (I thought it was automatically shared with the original owner).