Mastering Javascript Fundamentals: Recursion
Get the fundamentals down and the level of everything you do will rise. - Michael Jordan
As stated in my original post, I do 1 hour of video lessons from Watch and Code every day. If you're interested in learning Javascript in a way that goes beyond basic tutorials and gives you a foundational, practical knowledge without relying on frameworks - I'd highly recommend it. If you're reading these posts, please keep in mind that these are just my notes, and I'm not an expert (yet!). If your goal is also to master the fundamentals of Javascript, please head over to Watch and Code and start your journey there!
All screenshots were annotated using Shotty.
Recursion
First we can start with some simple observations:
1. Functions can see themselves.
2. Functions can call themselves.
Let's add a debugger statement before our function call to see what's happening.
In Chrome, when you type code inside the console, that code is put into an anonymous function that is run when you hit enter.
If we keep step into recurse, we see that we're in the body of the recurse function, and recurse is now at the top of the call stack.
We can click back and forth between calls in the call stack. When we do that we can see the scope change.
Typically when a function is done, it gets removed from the stack, so eventually the stack would be clear. But in this case it doesn't ever clear because each time recurse gets added to the stack, it calls itself and adds another call to recurse to the stack.
This will keep happening until it produces an error, which we saw in the console.
It tells us: "Maximum call stack size exceeded". Also known as a "stack overflow".
This is what happens when we don't make sure our recursive functions stop eventually.
So we can modify our second observation to:
Functions can call themselves, but we need to make sure they stop at some point.
We can see this play out in the debugger:
There is a slightly different version of this function that is a bit more common. We can just return the return value of recurse() without storing it to a "result" variable first. It's the same thing:
We can also look at factorials:
Using the debugger and a console beneath it, we can take notes through each of the steps to chart our journey through the successive function calls to the base case, and back out to the original call to factorial(3) with our values in hand on the way out.
Recursively unwrapping arrays
We can use this function to get to the center of any nested array:
Running examples like these through the array, we can watch the recursion in action as we go down to the base case, and then come back out with values.
Summary
- Recursion is when a function calls itself.
- Just calling itself will cause stack overflow.
- We need a recursive case and a base case to ensure that the function stops calling itself at some point.
- We can use this powerful concept to repeatedly call a function until we get to the base case, which returns a useful value, and then we come back out with that value, informing each step out until we have a final return value.
- We can see nice examples of this with factorials, and unwrapping arrays.