29
How Recursion Works: The Easy Way (No Fibonacci)
If you’ve struggled to learn Recursion by using fibonacci or exponential JavaScript functions, then this article is for you. I had trouble with recursion at first because there are almost 2 aspects of “math” based recursion: the actual recursion, and the ever changing return values. Luckily, if we remove the return values from the equation, things get a lot simpler. We can accomplish this by focusing on iterating through an array.
For a function to be recursive, it only has to do 2 things: 1) Call itself and 2) Know when to stop calling itself. That’s it, that’s all it takes. Technically, you don’t even need the second one. Sure, without it your function will explode, but it’ll explode recursively.
To start off, let’s make a base function. All it does is log a value in an array:
const recursiveFunc = (arr, idx) => {
console.log(`- ${arr[idx]}`);
};
const arr= ['a', 'b', 'c'];
// this would log each value
recursiveFunc(arr, 0);
recursiveFunc(arr, 1);
recursiveFunc(arr, 2);You might notice that the way to log each value is to call it with the index that’s one bigger. Right now we are the ones calling the function and incrementing the index, but what if the function itself did?
Let’s add the incrementing and calling inside the function.
const recursiveFunc = (arr, idx = 0) => {
console.log(`- ${arr[idx]}`);
recursiveFunc(arr, idx + 1);
};There it is: a recursive function. It looks odd to see a function call itself, but all programming languages are more than capable of doing this. However, if we ran this as is, it would blow up. That’s because we never tell it to stop at any point. We still need requirement #2, a stop condition:
const recursiveFunc = (arr, idx = 0) => {
if (arr[idx]) {
console.log(`- ${arr[idx]}`);
recursiveFunc(arr, idx + 1);
}
};Now, once we hit an index that’s not in the array, it won’t do anything and the whole chain of recursive functions comes to an end.
If you were to run this function, this is what you would get:
recursiveFunc(['a', 'b', 'c']);
// Logs out:
- a
- b
- cInternally though, this is what’s going on
As you can see, we keep increasing the value of our index by one each time, so we move through the entire array. While the index value changes, the array does not. Once there is no value at the index, the function has nothing more to do, so we exit out of the function, which then completes all the functions moving up the chain. Take a minute to really internalize the logic of what’s happening here, because this is the focal point of how recursion works.
Our function meets our definition of recursion, but it can’t iterate through nested arrays recursively. This is no good, since that’s actually one of the real-world applications for recursion. See, loops handle iterations better, but they can’t easily handle nesting of unknown depth. That’s because if a recursive function found another nested array, it can just call itself again on that array.
To account for nesting, all we need to do is add a step where we check if the value is an array. If it is, we start over at index 0, if not, we carry on as we normally would:
const recursiveFunc = (arr, idx = 0) => {
if (arr[idx]) {
if (Array.isArray(arr[idx])) {
recursiveFunc(arr[idx]);
} else {
console.log(`- ${arr[idx]}`);
}
recursiveFunc(arr, idx + 1);
}
};
recursiveFunc(['a', ['x', 'y'], 'd']);
// logs
- a
- x
- y
- dHere is a new version of our previous diagram:
What this does is start another chain of recursive calls on the new array. Look at how we pass in the new array and default back to
0 to start the new sequence. Once that sequence is done, we come back to our main chain. Also, notice that the final recursiveFunc call is after and outside of the array check. That’s because after we go down into an array, we always want to keep going when we come back up. For simplicity, we only nest once, but this could work with many more levels.To ensure you understand the main concept, why not try adding another parameter? Let’s add a level parameter for nicer printing:
const recursiveFancy = (arr, idx = 0, level = 1) => {
if (arr[idx]) {
if (Array.isArray(arr[idx])) {
recursiveFancy(arr[idx], 0, level + 1);
} else {
console.log(`${'- '.repeat(level)}${arr[idx]}`);
}
recursiveFancy(arr, idx + 1, level);
}
};
recursiveFancy(['a', 'b', ['q', ['x',]], 'c']);
// returns
- a
- b
- - q
- - - x
- cNotice where we
+1 idx and level, it’s not identical. We only increase level if we are dealing with a nested array, and we only increase idx if we are moving forward in an array. Now that the basics are done, it should be much easier to learn about recursive return values. Check out how they work with the fibonacci interview question. If recursion is so simple, why don’t we use it everywhere? Why are loops better for pure iterations? The reason has to do with the JavaScript Call Stack. I recommend checking it out, it’s a fundamental part of programming. But the long and short of it is: when you call a function, it gets placed on the call stack. Once it’s finished, it’s removed. But, the problem with recursion is that the first call can’t finish until all of the children functions finish. That means the call stack gets taller and taller. If it gets too high, it will all break.
That’s the issue with recursion, there is a maximum depth. You want one function that has a for loop that a million iterations? Neato. But a recursive function can start hitting issues way quicker. That doesn’t mean loops are better. It means we have to use recursion for more specific problems, like unknown depth or recursive data structures (Binary Search Trees). It’s just about finding the right tool for the problem.
Happy coding everyone,
mike
29