Recursion
I recently saw recursion explained by way of unstacking Babushka dolls and thought it was a great way of visualizing the process. Each doll is made up of the small doll within it, all the way down to the smallest doll. Essentially this follows the same pattern as recursive algorithm, where we solve a problem by solving a smaller instance of it until we reach an instance so simple/small that we can just solve it directly.
5! = 5 * (4 * (3 * (2 * (1)))))
This smallest instance is known as the base case of the algorithm and is crucial to a successful result. For example, when computing the factorial of n, the sub problems must get smaller and smaller until we compute the factorial of 1, which is simple and known to be 1 without any computation (you could also stop at 0! as either 0 or 1 are commonly used as a base case).
_.flatten
A more interesting application of a recursive function call is within this definition of a function that accepts a nested array of varying depth and returns the elements without the nesting. It checks each item in the list and if the item is nested, it recursively calls itself until a value is reached and plucks it out to concatenate it onto the end of the results array.
_.flatten = function (nestedArray, result) {
var result = [];
_.each(nestedArray, function (current) {
if (Array.isArray(current)) {
result.push.apply(array, flatten(current));
}
else {
result.push(current);
}
});
return result;
};
Recursion vs Iteration.
It may seem tempting to use recursion over iteration as less code is often involved and because the solution can appear to be more elegant. However, recursion in practice often turns out to be less efficient than its iterative counterpart. When the problem is very simple or not inherently recursive, or stack space available is limited, the iterative solution will prove to be a better choice.
Most iterative (looping) problems may be solved through either recursion or through iteration, such as given a non-negative int n, return the sum of its digits.
The iterative solution:
var sumDigit = function(num) {
var sum = 0;
while (num > 9) {
sum = sum + (num % 10);
num = Math.floor(num / 10);
}
return sum += num;
};
The recursive solution:
var sumDigit = function(num) {
if (num === 0) {
return 0;
} else if (num === 1) {
return 1;
} else if (num % 10 === num) {
return num;
} else {
return Math.floor(sumDigit(num/10)) + (num % 10)
}
};
Out of interest I ran these through a time tester using Chrome and got the following results:
So you can see that the recursive solution actually takes far longer to run!