Recognizing a Pattern in My Recursive Functions
Note: This was originally posted on my blog at https://therobinkim.com/blog/recognizing-a-pattern-in-my-recursive-functions. Any updates will appear there and not here.
Shawn Drost from Hack Reactor taught me to write recursive functions with an if-else statement:
function recursion() {
if(baseCase) {
// do something
} else {
// get me 1 step closer to the base case
}
}
As I was reviewing some of my curriculum material from Hack Reactor and thrashing about at codewars, I started to recognize a common pattern in my code when dealing with permutation problems that built on top of Shawn’s suggestion.
Here’s some code I would write if I had to find all the different permutations of a string called problem
.
function findAllAnswers(problem) {
var partialAnswer = "";
var allAnswers = [];
findAnswers(problem);
return allAnswers;
function findAnswer(problem) {
if(problem.length === 0) {
allAnswers.push(partialAnswer);
return;
}
else {
// add the first bit of 'problem' to partialAnswer
partialAnswer.push(problem[0]);
// explore all branches that include this first bit
findAnswer(problem.slice(1));
// lets remove what we added just before the recursive call
partialAnswer = partialAnswer.substring(0, partialAnswer.length - 1);
}
}
}
I used this approach to solve the N-Queens problem, list all possibilities of a rock-paper-scissors matchup, and find all permutations of words you could be typing into a T-9 cell phone numpad.
The key components that jump out to me are:
- I only have one
partialAnswers
variable that I manipulate until it meets the criteria for being a complete answer. Then I push the single solution to myallAnswers
array. - I explore all branches of the first possibility, then backtrack one step at a time until I return to my original state. At that point, I start exploring all branches for the next possibility.
- My code ends up being mostly simple and clean. I only need to worry about one parameter/argument in this simple problem. (My previous, unrefined approach would have required two arguments:
remainingProblem
andanswerSoFar
, which can be a bit of a mess to keep in order.)
The sorcery that happens in the else
statement is something I may have previously struggled to come up with, but now it feels like child's play. (That's good, right?)
Next up? Maybe tail recursion.