“To understand recursion, one must first understand recursion” - Unknown
Recursion is a method of solving problems where you solve smaller porti...
For further actions, you may consider blocking this person and/or reporting abuse
Thanks Christina! This helps my understanding of recursion. I'm going through a JS course right now and just came across this for the first time and was like "what?"
It makes me so glad to hear that this helped, best of luck with your studies! I'm curious which JS course you're taking...
The JS intro course on freeCodeCamp. I just discovered CodeWars as well, which I'll throw in there to break things up. Near the end of the JavaScript Introduction part of the course and just got into recursion. I have not figured out the solution yet but your article has helped.
Hasn't heard of CodeWars before but I started programming on freeCodeCamp so I'm a big fan of their courses! Good luck!
Thanks! Have you made it through their entire course offering? (Before Python's update I mean)
Not yet, only the responsive web design and JS algorithms ones so far. I've taken several other courses through Coursera, Scrimba, and Codecademy though. There are so many excellent, free resources or there!
True that! I've done free versions of Codecademy before - that was my first HTML course almost a year ago today. Ah the memories.
Welcome to the world of programming, Aaron -- I used to hate recursion because it was not intuitive to me at all no matter who explained it. When I learned it there weren't such abundant resources. It took me years to come back around to learning it (all the while hoping no one around me would find out that I couldn't do it)
Here are a few things that may help with some lingering questions (e.g. when to use it?). Whenever you've a problem and the only thing that comes to mind as the answer the problem is to "enumerate" or "try all possibilities" or an "exhaustive search" is usually a signal for recursion, because the recursive parts are probably repetitive...
One thing that I was aware of, but wish someone had really forced me to understand was thinking about how to do recursion in terms of a decision tree aka recursive tree -- "in my current position, what are my options?"
With Fibonacci, we have two branches (i.e. two decisions) at EVERY (node) call with one exception (base case) when the value that comes into our function is
0or1Drawing this out by hand is an exercise that has made it click for me. While I can mostly do this in my head now or in a comment in the code, if I can't determine what my decisions and exceptions are, then I cannot write the code
Thanks David! I appreciate this. 😊
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.
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
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
fibIterativeis the top-down approach, and thefibOptimalis 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...It's good to know you can do all recusive algorithms iteratively also, I had always wondered.
Your example above does not iterate unless you change n > 1 not n < 1, it had me going for a bit you and should always test your code ;-)
function factorial(num) {
let total = 1;
for(let n = num; n > 1; n--) {
total *= n;
}
return total;
}
Oops, thanks for pointing that typo out, I've made the change in the post.
I was dreading learning recursion, but this write up helped for it to click.
Thank you!
That makes me so happy to hear since I've been in your shoes too!
i absolutely love recursion! it could be a bit tricky to wrap your head around, but once you get the gist of it, things just are more simpler and elegant
Yes! I love how recursion appears in so many walks of life: programming, math, art, nature, etc. MC Escher is one of my favorite artists due to his use of recursion!