Also, for some algorithms, an iterative solution may not be an option.
Actually, that's false. Anything that can be implemented with recursion can also be implemented with iteration. After all, the CPU doesn't know recursion -- it only knows jump instructions. So every recursive function in a high-level language eventually gets translated into an iterative subroutine.
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...
Actually, that's false. Anything that can be implemented with recursion can also be implemented with iteration. After all, the CPU doesn't know recursion -- it only knows jump instructions. So every recursive function in a high-level language eventually gets translated into an iterative subroutine.
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...The following booklet contains a few problems solved with both recursion and also iterative approach:
codeguppy.com/site/download/recurs...
On the same site you can also explore the following two playgrounds with problems solved with both recursion and iterative approach:
Flood fill
codeguppy.com/code.html?t=flood_fill
Find element in a hierarchical structure
codeguppy.com/code.html?t=find_max