Reducing reduce: Recursion & ES6
Coding challenges and websites abound and I enjoy tackling new problems, but sometimes it is fun to tweak or improve old toy problems and come up with alternate creative solutions. It is especially cool if you can do so with even less code. One way I like to challenge myself is to solve problems using recursion, not always because it is better, but simply because I like recursion. This can lead to difficulties because some problems are more efficient with a simple 'while' loop, but recursion is still fun. Another common challenge I give myself is using 'reduce' or 'reduceRight' in a solution. The extra level of abstraction is almost always more fun than standard loops.
Recently, a friend told me about a refactoring puzzle that incorporates both of my favorite additional challenges. He was asked to reimplement 'reduce' in JavaScript using recursion! To top it off, he was told to do it in two lines. Well, I was eager to solve this problem and below I'll break it down.
var reduce = function (collection, callback, startVal) {
var initVal = arguments.length > 2;
collection.forEach(function (element) {
if (!initVal) {
startVal = element;
initVal = true;
} else {
startVal = callback(startVal, element);
}
});
return startVal;
console.log(
reduce(
[1, 2, 3, 4, 5],
function (a, b) {
return a + b;
},
1
)
); // 16
};
Above you can see a basic implementation of reduce. The function checks whether an initial value is passed into the invocation using the '.length' method on the arguments object. If not, the start value is set to the first element in the collection. The provided callback is invoked on the start value and each element of the collection. The 'startVal' is reassigned to the return value of the callback on each iteration. Finally, the startVal is returned after each item in the collection has been reduced or folded using the provided callback. Now let's try to refactor so that it is only two lines of code and uses recursion. For this challenge, I'll also use some ES6!
let reduce = (collection, callback, startVal = 0) => {
if (collection.length === 0) return startVal;
return reduce(collection, callback, callback(startVal, collection.shift()));
};
console.log(
reduce(
[1, 2, 3, 4, 5],
function (a, b) {
return a + b;
},
1
)
); // 16
The body of this solution is only two lines of code! We remove the initial agruments test by using the new ES6 'defaults' in the parameter. (This isn't as comprehensive because it defaults to zero instead of the first item in the collection, but it will work for an array of numbers) The function can now start with a base case which ends the recursion when the length of the collection is equal to zero. The reduce function is then called recursively passing in the collection, the callback, and the reduce magic. The startVal is reassigned to the return value of the callback within the recursive invocation. The startVal
from the previous call is the first parameter in the callback invocation, and using the .shift
method, the second parameter is set to the first item in the array. Since, arrays are in memory objects, when .shift
is called, the array shortens by one and moves it one step closer to the base case!
There you have it, reduce in two lines using recursion and ES6! What other fun refactors might be possible?