DEV Community

Discussion on: Recursion Explained (with Examples)

joshuakb2 profile image
Joshua Baker

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.

christinamcmahon profile image
Christina Author

Thanks for pointing that out and for the explanation, totally makes sense! I've gone ahead and taken it out :)

wulymammoth profile image
David • Edited on

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:

codeguppy profile image

The following booklet contains a few problems solved with both recursion and also iterative approach:

On the same site you can also explore the following two playgrounds with problems solved with both recursion and iterative approach:

Flood fill

Find element in a hierarchical structure