What's this "recursion" I keep hearing people talk about? That's a question I got the other day. Recursion is a concept that has (unfairly, I think) gotten a reputation for being difficult to understand. It's really not hard, it's just a little different than what you'd normally see.
Here's an example of the same function written two ways: first with a loop, then using recursion. In this case, we have a web page with a choice list showing several local cities. We don't want to show any favoritism (nor, apparently, do we want to be usable), so we'll randomly reorder the list of cities each time it's shown:
var cities = ['San Diego', 'Solana Beach', 'Del Mar', 'La Jolla', 'Jamul', 'Chulajuana', 'Sorrento Valley'];
cities = randomize_loop(cities);
gs.log(cities);
cities = randomize_recursive(cities);
gs.log(cities);
function randomize_loop(arr) {
var answer = [];
while (arr.length > 0)
answer.push(grab(arr));
return answer;
}
function randomize_recursive(arr) {
if (arr.length == 0)
return [];
var item = grab(arr);
var answer = randomize_recursive(arr);
answer.push(item);
return answer;
}
function grab(arr) {
var rm = arr.splice(random_int(arr.length), 1);
return rm[0];
}
function random_int(bound) {
return Math.floor(Math.random() * bound);
}
In this example, the recursive function is actually slightly longer than the loop-based function — more commonly, the recursive approach results in shorter code.
The loop function iterates through grabbing elements randomly from the input array until there are no more elements to grab. Each element grabbed is pushed onto an answer arrary, and that answer array is returned. Simple enough.
The recursive function first just returns with an empty array if its input array is empty. This isn't just an optimization; this is how the answer array gets created. If the input array has at least one element, then the recursive function grabs a random element from it. After that is where the recursion takes place: it then invokes itself with the shortened input array. Then it pushes the item that it grabbed onto the answer from the recursive invocation and returns with it.
The test code above has seven elements in the input array. When we first call the recursive function, it will grab a random item and invoke itself with the six remaining item. This invocation will again grab a random item, and then invoke itself with the five remaining items. This is almost exactly what happens in the case of the loop function — but without the loop! This recursive behavior continues until finally on the seventh invocation it grabs the last remaining item and invokes itself with no remaining items. This time the function simply returns with an empty array. At that time, the code after the seventh recursive invocation is returned to (the line "answer.push(item);"), and the item it grabbed is pushed onto the answer array. This behavior continues through all the invocations, in reverse order, as the call stack is unwound back to the original invocation, which then returns to the original caller with the answer.
When should you use recursion? If you understand recursion well, you'll find there are times when using a recursive approach results in much simpler code. I generally start thinking about recursive approaches when I find myself with complicated loops, or loops within loops. The (unfortunate) fact that so many people don't understand recursion, or are uncomfortable with it, means that you may want to stay away from it unless the benefits are too compelling to ignore...
