Junior Developer at Interplay Learning - Feel free to contact me via LinkedIn or connect on Github, I am always happy to chat with folks from this community!
In fact, what Josh notes is actually what's done in practice most of the time (when possible) and what you've done turning your recursive solution into a "memoized" version. For big company interviews, these types of questions are becoming common-place -- where recursion (already a challenge for some) is the brute force method, but with a large enough input would result in an overflow of the call stack. This optimization that you've done is often known as "dynamic programming" and while Fib is the classic example, there are certainly some problems that require some exceptional thought to convert from standard recursion (much more elegant IMO) to one that's iterative (DP) and you can certainly find tons on Leetcode. I wouldn't worry too much about it unless you're super curious -- took me forever to learn.
There's also one "in-between"/hybrid memoized version -- in "dynamic programming" there are typically two approaches as well: 1) top-down, 2) bottom-up. I wrote a gist (in JS) for a friend trying to understand it a couple months back: the fibIterative is the top-down approach, and the fibOptimal is similar to yours but instead of two well-named variables that you have, I've stuck them in a two-element array/tuple: gist.github.com/wulymammoth/bdb5e3...
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Thanks for pointing that out and for the explanation, totally makes sense! I've gone ahead and taken it out :)
In fact, what Josh notes is actually what's done in practice most of the time (when possible) and what you've done turning your recursive solution into a "memoized" version. For big company interviews, these types of questions are becoming common-place -- where recursion (already a challenge for some) is the brute force method, but with a large enough input would result in an overflow of the call stack. This optimization that you've done is often known as "dynamic programming" and while Fib is the classic example, there are certainly some problems that require some exceptional thought to convert from standard recursion (much more elegant IMO) to one that's iterative (DP) and you can certainly find tons on Leetcode. I wouldn't worry too much about it unless you're super curious -- took me forever to learn.
There's also one "in-between"/hybrid memoized version -- in "dynamic programming" there are typically two approaches as well: 1) top-down, 2) bottom-up. I wrote a gist (in JS) for a friend trying to understand it a couple months back: the
fibIterative
is the top-down approach, and thefibOptimal
is similar to yours but instead of two well-named variables that you have, I've stuck them in a two-element array/tuple: gist.github.com/wulymammoth/bdb5e3...