How to Not Curse Using Recursion
I think for people who are learning to code, recursion is one of the hardest concepts to grasp. I know for me, at one point in time, the thought of calling a function inside of itself made me want to curl up in a ball and cry myself to sleep.
Thankfully, I eventually realized that just because recursion is difficult, it didn't mean that I should abandon trying to use it. While, often times, there are alternate ways to solve a problem, recursion is an incredibly useful method for arriving at a solution.
The key to getting better at it is to learn how to spot the types of problems where recursion can be used. Once you can recognize those types of problems, learning the patterns for how to use it will help you to improve. So, let's explore this a bit further.
Common problems solved by recursion
In simple terms, recursion is the act of calling a function inside of itself. While that concept may not be hard to grasp, it may not be so clear why that would be useful.
Basically, using recursion helps us to continuously modify, evaluate, and/or return values. This is especially useful when you have an unknown number of values to evaluate or do something with. For this reason, you can also frequently solve these types of problems iteratively by using a for loop to arrive at a solution.
Let's look at an often used example for a factorial:
var factorial = function(number) {
/*
For reference, a factorial is the product of an integer and all
of the positive integers below it. So, the factorial for 4,
referred to as 4!,would be (4 * 3 * 2 * 1).
*/
if (n === 1) { // This condition is the *base case*.
return 1; // the base case is what we need to stop the function
} // from calling itself again. Without it,
// the function will call itself infinitely
// and the computer will crash.
if (n < 1) { // This is a check to ensure that the user
// did not pass us a bad value, like 0 or -2
return "Error! Please submit a positive value";
}
else { // This is the case where the recursion happens.
// Notice that we call the function below with a lower value.
// This will allow us to eventually reach a point where we
// pass the function '1' and it will no longer be called.
return n * factorial(n-1);
}
};
What's important to note here is that the interpreter always returns a value when this function is called, even though it only will return the final value to the user. So, when you pass factorial a value of 5, the interpreter will first check to see if 5 meets the first two conditions. When it gets to the last conditional, the interpreter will return 5 but it will now go through the same process with 4 (since n - 1 is 5 - 1 in this case). It will continue to return values that are being multiplied until it gets to 1, at which point the function will no longer be called.
So, inside the interpreter, this is what happens when we run factorial(5):
return 5 * factorial(4)
return 5 * 4 * factorial(3)
return 5 * 4 * 3 * factorial(2)
return 5 * 4 * 3 * 2 * factorial(1)
return 5 * 4 * 3 * 2 * 1
Beyond math, recursion is especially powerful when evaluating arrays and objects organized into lists. Consider a problem where you would have to find the maximum value in an array of [2,1,3,9,5,7]. You can clearly use a for loop to determine that the answer is 9, but let's look at a solution using recursion:
var maximum = function(array) {
// If the user submits an empty array, we return null
if (array.length === 0) {
return null;
}
// result is set to the first item in the array
var result = array[0];
/*
Much like a for loop, we use recursion on an inner function here
to check each item in the array. checkValue() stops recursing
when the index is equal to the array's length.
*/
var checkValue = function(index) {
if (index === array.length) {
return;
}
else if (array[index] > result) {
// Below, we set the result to the array item
// if it is larger than the current value of result.
result = array[index];
}
// We increment the index by 1 to move to
// the next item in the array.
checkValue(index + 1);
};
// Now, we call the inner function to start the loop.
// We will start the function at index 0.
checkValue(0);
return result;
};
maximum([2,1,3,9,5,7]); // returns 9
One thing worth noting here is the use of the inner function, checkValue. Rather than going through the trouble of calling the main function, I used recursion, instead, on the inner function. Thanks to the concept of closure, I can now constantly update the "result" variable every time the inner function runs.
Since the result variable is declared outside of the inner function, it won't be reset to it's initial value every time the inner function is invoked. Instead, it will maintain whatever value it has been set to prior to each function invocation.
For that reason, it is my belief that using inner functions is probably one of the best ways to get better at finding recursive solutions.
Why recursion is actually useful
There's still one problem though. This solution is inefficient. It's no better than doing a simple for loop and it probably took longer to think of. Plus, while you can use inner functions in JavaScript to modify variables in the outer scope, you can't always do that in other languages.
Wouldn't it be better if we could make this code shorter than a for loop solution and still use logic that's applicable in other languages? In fact,we can do this by using recursion on the main function:
var maximum = function(array) {
if (array.length === 0) { // Our base case
return null;
}
return Math.max(array[0], maximum(array.slice(1)))
};
maximum([2,1,3,9,5,7]); // returns 9
As you can see, this solution is much shorter than the previous solution and we didn't create any side effects by using an inner function to modify variables in the outer scope. This is the whole point of recursion: you can make code a lot smaller and problems a lot simpler by using it.
Here, it's worth it to look at what's happening in this code as the interpreter runs:
var arr = [2,1,3,9,5,7];
maximum(arr);
// Let's look at how this code executes at every step
return Math.max(2, maximum([1,4,8,5,7,3])) // At every step we send
return Math.max(1, maximum([4,8,5,7,3])) // the interpreter a
return Math.max(4, maximum([8,5,7,3])) // shorter array
return Math.max(8, maximum([5,7,3]))
return Math.max(5, maximum([7,3]))
return Math.max(7, maximum([3]))
return Math.max(3, null) // Our first call we can evaluate
// Now that we have a value returned, we can begin working
// our way back up the chain to evaluate all the previous calls
return Math.max(3, null) // returns 3
return Math.max(7, 3) // returns 7
return Math.max(5, 7) // returns 7
return Math.max(8, 7) // returns 8
return Math.max(4, 8) // returns 8
return Math.max(1, 8) // returns 8
return Math.max(2, 8) // the original call now returns 8;
Basically, what we have done is shorten this problem into a process of comparing each pair of two numbers in the array and returning the greatest value. How much cooler is that?
What's helpful to remember here is that you can improve your understanding of recursion by simply listing out what's happening in the interpreter at every step.
Advanced (and extremely cool) example of recursion
Now that we've seen an example of how you can use recursion to evaluate items in an array, let's have a little bit of fun by seeing if we can use recursion to find all the possible 4 digit combinations to unlock a phone.
Remember, recursion is often a replacement for an iterative solution. To find all the combinations, we will create solutions methodically, first doing 0000, then 0001, and so forth. Using recursion here will allow us to combine the first digit from 0-9, with all numbers from 0-9 for the second digit, and then repeat the process for the third and forth digit.
This is what the code might look like if we used an inner function:
var unlockPhone = function(password) {
// This function unlocks the phone if it receives the correct password.
if (password === '0927') {
console.log('Phone unlocked');
return true;
}
else {
console.log('Invalid password. Please try again');
return false;
}
};
var findPassword = function(n) {
// n represents the number of digits that the password needs to be
var combinations = []; // This will store all the combinations
// We will build strings of all possible number combinations
var numbers = ['0','1','2','3','4','5','6','7','8','9'];
// This inner function is where the magic happens
var generatePasswords = function(numbersLeft, result) {
if (numbersLeft === 0) { // The base case
combinations.push(result);
return;
}
for(var i = 0; i < numbers.length; i++) {
// Note that concat is the same as push except
// that it returns the modified array while push
// returns the length of the modified array
generatePasswords(numbersLeft-1, result.concat(numbers[i]));
}
};
generatePasswords(n, []); // The recursive call
// The inner function will be passed an empty array at the start
// it will then build a four digit combination and push that to
// the combinations array.
return combinations;
};
var tryPasswords = function(combinations) {
// Once we have all the possible combinations, we can use a for loop
// to check all the passwords.
var password;
for(var i = 0; i < combinations.length; i++) {
password = combinations[i].join('');
if (unlockPhone(password)) {
return password;
}
}
// This last part only executes if the for loop doesn't return
console.log('Incorrect password. Please try again');
return null;
};
var solutions = findPassword(4);
// returns an array of 4 digit combinations
tryPasswords(solutions);
// logs 'Phone unlocked' then returns '0927'
This solution works and is a completely valid way to solve the problem in JavaScript. However, we can also refactor findPassword() to a solution where we only call the main function.
Let's check that out:
var findPassword = function(n) {
if (n === 0) { // base case
return [[]];
}
else {
var temp = findPassword(n-1);
var solution = [];
for (var i=0, len = temp.length; i < len; i++){
for (var j=0; j < 10; j++) {
solution.push(temp[i].concat(j.toString()));
}
}
return solution;
}
};
findPassword(4)
// returns our correct solution array
Now, we have a solution that could be reimplemented in other languages like Python and it's more elegant. Why does this work though? Let's take a look at what happens in the code as we execute it:
findPassword(4);
// When the function starts executing, it first gets to the else
// Then it looks to define temp, which is
var temp = findPassword(3)
// What the interpreter does here is create an execution context
// to evaluate this statement. If you don't know what an execution
// context is, it just means the interpreter will come back to it later.
// The calls inside the interpreter will proceed like this:
var temp = findPassword(3) // now calls the function with 3
var temp = findPassword(2) // now calls with 2
var temp = findPassword(1) // now calls with 1
// Note that we still haven't gotten to evaluate the rest of the code.
// Finally, we get to:
var temp = findPassword(0) // At this point, we get returned [[]]
// All of the previous calls still must be evaluated separately,
// but for now let's look at how this executes
// The variable temp is now equal to [[]]
// The for loop executes since temp.length === 1
// and the other for loop will execute like so:
solution.push['0']
solution.push['1']
solution.push['2']
// ... and so forth until ['9']
// we then return that solution array, but it doesn't get
// returned to the abyss, it gets returned for findPassword(1)
// Now, temp equals [['0'],['1']...['9']]
// So, when we execute the for loop this time, solution gets
// pushed a lot more. It still starts as an empty array.
// But this is what it now looks like:
[['0','0'],['0','1'],['0','2']...['9','9']]
// This larger array of more combinations now gets
// returned as findPassword(2), and temp becomes that
// within the function call of findPassword(3)
// This continues until we evaluate our final call for findPassword(4)
This solution can be harder to understand, so if you're trying to get better, I would suggest starting with using inner functions to solve problems and then working your way up from there. If you make sure to write out what's happening at every step, it will get easier over time.
Rapper turned Soldier turned Software Engineer
