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.
Recursively mapping arrays
Let's create a simple formatMoney function that will take any number or array of numbers and return a string formatted with a dollar sign:
// Example input => output: // 1 => '$1' // [1 , 2, 3] => ['$1', '$2', '$3'] function formatMoney(numbers) { if (Array.isArray(numbers)) { return numbers.map(function(element) { return '$' + element; }) } else { return '$' + numbers; } }
We can use it like this:
formatMoney(1); // "$1" formatMoney([1, 2, 3]); // ["$1", "$2", "$3"]
Where this function fails is when we have nested arrays. It fails to maintain the array structure:
formatMoney([[1], [2], [3]]) // ["$1", "$2", "$3"]
What we want is:
[[1], [2], [3]] ==> [['$1'], ['$2'], ['$3']]
The reason we're getting the bad behavior above is that if you add a string and an array, Javascript rips out the inner element and turns it into a string. Here are some examples:
'$' + [1] // You might think you get '$[1]' // "$1" <= instead you get this '$' + '1' // "$1" '$' + [[[1]]] // "$1" // This is all because JS is calling toString on the array and ripping out the inner element. [[[1]]].toString(); "1"
How can we modify format money so it respects the array structure, like in this comment:
// [[1], [2], [3]] ==> [['$1'], ['$2'], ['$3']]
Well we can break our function body out into our two cases: Recursive case and Base case. And in the recursive case we can call formatMoney again within the callback function of .map.
function formatMoney(numbers) { // Recursive case. if (Array.isArray(numbers)) { return numbers.map(function(element) { // return '$' + element; return formatMoney(element); }); // Base case. } else { return '$' + numbers; } }
Now it works as expected in all these cases:
formatMoney(1) // "$1" formatMoney([1]) // ["$1"] formatMoney([1, 2, 3]) // ["$1", "$2", "$3"] formatMoney([[1], [2], [3]]) // [["$1"], ["$2"], ["$3"]]
The key insight here is that we have an unknown depth problem: we don't know how many array layers there will be, so we use recursion to unwrap each layer until we hit the base case where it stops.
A helpful visualization of the call stack when calling formatMoney([1]):
It's good to go through this diagram exercise above to get a concrete understanding of what's happening.
Observations about recursion
Identify the base case and recursive case.
The recursive case needs to get closer to the base case each time. For example, we need to unwrap one array layer at a time until we get to the element.
Steps to recursive mastery
The people who use recursion a lot have seen a lot of recursive code. Then when they come to a problem, they pull from things they've seen in the past.
See enough code so that it becomes "another one of those".
Summary:
- We can use recursion to solve unknown depth problems
- Here we use it format values within arrays while still maintaining the original array structure.
- We combine .map and a recursive call within .map's callback function to do this.
- Diagramming the call stack is great way to understand and visualize the journey to the base case.
- We can then use the debugger to let that journey play out for real and check our understanding.