Algorithms for beginners: fundamentals of recursion.
Recursion is the one idea I constantly use while I solve coding problems. Most of the time I don’t start by thinking “RECURSION WILL SOLVE THIS!”. However recursion just ends up being the logical way to reach an answer. In my professional opinion recursion is the purest form of coding; write a function that will call itself until you get what you want! To implement recursion we will create a helper algorithm. 1) Identify what the smallest input is. 2) Continually break down a larger input into smaller inputs and pass those smaller inputs back into itself until you get the desired answer. 3) Define a "base case" that will stop the Recursion should the answer not be found.
Let's look at the idea of Recursion first. We are writing code that will execute itself until we get a desired answer or reach a base case. Essentially we are creating a loop. I will illustrate this with pseudo code:
for (let recursion =()=>{ …answer? answer = true : false} ; answer === false; recursion())Much like a traditional for loop the above pseudo code will continue while the second condition is true; the recursion will continue until answer === true. At this point the second statement of the for loop is false terminating the loop. Above if answer === false recursion will call itself again. This is the general idea of recursion. This is why creating a base case is essential to prevent an infinite loop. The “answer” we are looking for might not be present causing recursion to run until the sun burns out.
Let’s walk through a real example of Recursion
Digital Root is a classic algorithm problem given as a challenge to test your coding skills. In it you take the sum of all the isolated integers in a number until you reach a single solitary digit.
For example the digital root of 16 is 7. You isolate “1” and “6”, add them together and get “7”. This is a single digit and thus the answer. Recursion is an obvious way to reach the digital root. Let’s use our helper algorithm:
The smallest input will be a single digit. We will break our larger input into smaller inputs, i.e. We will start with “1” and “6” and add them together giving us “7”. “7” is a single digit and thus the answer we wanted.
However if our starting input was "942" we would break this down into “15” which gets recursively passed back into the function.
function digital_root(n) {
let stringifiedNum = n.toString().split("");
if (stringifiedNum.length > 1) {
//above we check to see if we have not reached the answer.
let reduced_answer = stringifiedNum.reduce((acum, cur) => { return acum += parseInt(cur) }, 0);
//we go through the process and add our isolated integers into a summed up number
//we then pass this sum into ourself again.
digital_root(reduced_answer)
} else if (stringifiedNum.length === 1) {
//here we have reached our base case and the answer
//we then return out of the function and exit the function
return stringifiedNum[0]
}
}While writing these problems it’s important to understand what JavaScript is doing. We wrote the code and know what it is doing but do we know HOW. It seems like a “no brainer” but there are implications to calling yourself.
When you call a function in javascript it is put onto the execution stack. Recursive function calls build up on the execution stack call by call until we reach the answer or base case; JavaScript is LIFO (last in first out). In an example of 942. In this case “942” gets passed into the function digital_root(942).
This function call is put on the stack then the function calls itself putting digital_root(15) on the top of the call stack over digital_root(942). Here digita_root(15) will hit our basecase digital_root(6) and the answer of a single digit. JavaScript will popoff digital_root(6) from the execution stack, then (15) then lastly popoff digital_root(942).
As an aside our function digital_root relies on iteration with reduce; It iterates through every element of the data structure being passed to it. It is important to realize that most recursive functions can be refactored to use iteration and conversely most iterative processes can use recursion.
Many times iteration would be more performant if the input is small. If you want to read further you can check out javascript recursion stack, and this great blogpost on recursion vs iteration. As a challenge can you use pure iteration to solve this?
Don't just skip over this and actually try it. Dan Abramov, the creator of Redux, had an email subscription that proded his readers to "do their homework". I took a lot of value from this and it taught me quite a bit. I will challenge you to do this as well. If not me do it for Dan Abramov.
To move up a meta level recursion is the very reason human beings have climbed to the top of the food chain. We “call” ourself until we get our desired result. Weather it satisfy our own hunger or writing the perfect algorithm we call ourselves while we are not satisfied. It’s also one more reason why I love recursion.