Recursion is a concept that can be made easier if you have an easy way to think about it, and what it is you’re actually doing. For this discussion, I’ll be considering the Fibonacci function, which returns a number that is the result of adding the two previous fibonacci numbers. This function is bound by zero, so starting at zero you’ll get:
f(n) = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Here’s what it looks like:
var fibberfunk = function(n){
if (n > 2) {
return fibberfunk(n-1) + fibberfunk(n-2);
} else {
return n;
}
};
1. It’s turtles all the way down… until you’re at the base:
A recursive solution is suitable for the types of problems that require you to support your next result with the outcomes of previous invocations of your function. Like the old story of what supports the flat earth, recursion can go on and on indefinitely. Unlike the fable, however, we must have a base case or our recursions will fall apart. At the base case, your recursion stops recursing and finally begins to really operate. So you always need to make sure that you have a “base case” to stop the function from depending on itself for any more arguments. In the Fibonacci example, the base case is contained in the else statement: When n <= 2 return n.
By returning a value which doesn’t require any further code execution, you enable the recusion to stop. Your base case is the first solution that your code will reach, and it’s the result which will support the final results. It’s often easiest to think of the base case as the bottom, but that won’t always be true.
2. Always send flowers (unless you don’t have to):
In life, flowers serve the function of reminding the recipient who sent them. (Yes, they serve other functions as well, but for the sake of this discussion I’m using them as a literary device.) In this example, they serve the purpose of reminding you to ALWAYS MODIFY THE INFORMATION YOU’RE PASSING FORWARD. When you’re not at your base case, you have to send flowers to the next step of the function in order to set the stage for future invocations to reach the base case. In the above example, our flowers are sent by the returnstatement when n > 2:
return fibberfunk(n-1) + fibberfunk(n-2);
Notice that each successive function calls the same function with a modified argument. In our case, we’re reducing the value of the argument we’ve passed in which brings us closer to our base case of having n <= 2. By modifying the argument we pass to subsequent invocations of the function, we’re “sending” information… in our case, the information we’re “sending” is that we’ve taken one step closer to the base case. This is called the “recursive case” and you might have more than one type of recursive case in your function, in ours there is only one.
It’s very, very important that you send flowers, or your function will never know when it’s reached the base case.
3. Recursion is not iteration
The last trick I want to share is not so goofy, but I think it should be taken seriously. I tend to remind myself that recursion isn’t the same as iteration so I don’t create for loops to solve recursion problems. In an iterative function, we say something like this:
var shmiterative = function(num) {
for (var i=0; i < num; i++) {
return num + 2;
}
};
schmiterative(5);
//3
//4
//5
//6
//7
While we are passing information forward through the for loop, by incrementing the index, notice that schmiterative(); is not dependent on the result of the base case to be able to calculate all the other results. Our incrementation will continue indefinitely until i = num but we’re able to calculate the result of every return statement without relying on the result of the base case.
Let’s hope that any of the tricks will help you get a little bit closer to solving your own recursive riddle, and if you’ve got some suggestion of how to improve or correct anything I’ve written, please let me know.