re: Recursion Algorithm Practice: Fibonacci Sequence Generator VIEW POST

TOP OF THREAD FULL DISCUSSION
re: They want to see that you understand memoization, and that you have a general idea how big its impact can be for a problem like computing fibonacci...
 

For sure! I ran your suggestions through the same series of tests the others have gone through so far and came up with the following:

If you take a look at my first solution that deals with iteration rather than "true" recursion, the 3 variables used are a stand-in for the dictionary known as a form of memoization, giving us the performance boost of allowing our previously known values to be stored and re-assigned with each iteration, rather than stored separately in an ever-growing dictionary. I find this way of going about it simply more to my personal taste because we are never allocating more RAM than those three values take up combined on that particular pass through the loop. But, if we needed to not only find the nth fib number but also store all previous fib numbers up until that point, I wouldn't have even considered using a dictionary as a cache so thanks for pointing out that use case to me because I'm sure they will want to know these types of solutions with "one-off-calculation" use cases, as well as persistent, referenceable use cases.

Also, using "true recursion" is the better solution for numbers of passes in the hundreds. But the use-case I'm gunning for (hundreds of thousands of passes), true recursion hits that stupid Python depth limit well before I can get where I want to go. The iterative solution is a nice, safe, and quick-to-implement O(n) algo that I can write quickly, debug with minimal fuss (or really, no fuss) and have the peace of mind that I know what I'm going to get with a fairly predictable, linear increase in execution time with an increase in the dataset's size.

code of conduct - report abuse