DEV Community

loading...

Discussion on: Recursion Explained (with Examples)

Collapse
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.

Collapse
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 :)

Collapse
wulymammoth profile image
David

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...

Collapse
codeguppy profile image
Adrian

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