Sunday, 26 January, 2020 UTC
Summary
In this article, you’re going to learn how to use recursive programming, what it is, and how to optimize it for use in algorithms. We’ll be using JavaScript as our programming language of choice to understand the concept of recursion.
Prerequisites I’ll be using Big O Notation to compare optimization strategies, which you can brush up on here.
What is Recursion? Recursion is any time a function calls itself inside itself, potentially creating a infinite loop. If you’ve ever worked with canvas animations then you’ve already used recursion since we use an
animate function that updates our animation before rerunning itself.In the below example, we’re passing in a number, doubling it, then passing that value to itself again. In theory, this would continue forever but because computers are limited we generally can’t have infinite recursion. You’ll get an error like
too much recursion or Maximum call stack size exceeded if you don’t include some exit condition to stop the function, in the following case as soon as it’s over 100:const double = num => { num = num + num; console.log(num); if (num > 100) return 'Exit'; // Try removing this return double(num); }; console.log(double(4)); You’re probably thinking, “that’s cool and all, but can’t I just use a loop for anything recursion can do?”. Well yes, but actually no. Recursion comes in handy when dealing with various searching and sorting algorithms or traversing data structures that are more complicated than simple lists. When done correctly, you can also get much better performance, like O(log n) while all loops are O(n).
↓ Here's a great JavaScript course we recommend. Plus, this affiliate banner helps support the site 🙏
You don’t have to play around with recursion for long to realize that it’s pretty easy to overwhelm your computer. This is because most recursive functions are O(n^2) or even O(n!). Since JavaScript runs on call stacks every time a new recursive layer is added, a lot of memory and processing power must be used to manage it all, despite most of it being redundant.
Let’s try something simple like generating a fibonacci sequence. A fibonacci sequence is where every digit is the sum of the two items before it, 0, 1, 1, 2, 3, 5, 8, 12…
const fibonacci = num => { if (num < 2) return num; return fibonacci(num - 1) + fibonacci(num - 2); }; for (let i = 0; i < 1000; i++) console.log(fibonacci(i)); // 3 minutes before page crashed... That’s just horrendous. Using up resources for 1,000 layers of the same information is too much even for my, relatively, decent computer.
Instead, we can work around this by adding a storage variable, or a “memo”, that will contain our values as the stack progresses. Every time our function runs, its value will be added to its corresponding index in the memo and the next layer will refer to that to calculate our result.
const fibonacci = (num, memo) => { memo = memo || {}; if (memo[num]) return memo[num]; if (num < 2) return num; return memo[num] = fibonacci(num - 1, memo) + fibonacci(num - 2, memo); }; for (let i = 0; i < 1000; i++) console.log(fibonacci(i)); // 143 Milliseconds Let’s try applying this to another recursive function. This takes a number and outputs its factorial, so 3! should return 6 because 3x2x1=6.
const factorial = n => { let num = n; if (n === 0) return 1; for (let i = 0; i < n; i++) { num = n * factorial(n - 1); }; return num; }; console.log(factorial(3)); // 7 Milliseconds console.log(factorial(6)); // 8 Milliseconds console.log(factorial(9)); // 15 Milliseconds console.log(factorial(12)); // 11,588 Milliseconds For me, anything above 12 crashes the page because this function has the complexity of O(n!) as each layer in the stack has to handle the complexity of the one before it.
Instead, let’s try memoizing it and see the difference.
const factorial = (n, memo) => { memo = memo || {}; if (memo[n]) return memo[n]; if (n === 0) return 1; for (let i = 0; i < n; i++) { memo[n] = n * factorial(n - 1, memo); }; return memo[n]; }; console.log(factorial(12)); // 4 milliseconds console.log(factorial(120)); // 12 milliseconds console.log(factorial(1200)); // 24 milliseconds console.log(factorial(12000)); // 1408 milliseconds I don’t know about you, but I think that’s an incredible improvement, it can now handle 10,000 times the computations in 1/8th the time.
Closing Thoughts Recursion is one of those things you need to get very comfortable with because it will return repeatedly, or haunt you, throughout your programming career. It will be essential for learning to traverse trees and lists and sort various data sets in the future.