Looping without Loops

I ran into an interesting JavaScript puzzle today.

Write a function that when passed an Array of integers will return the subset of evens without using loops (for...in, while, etc.) including builtin prototype methods that use loops.

There are two problems to solve here. The first is easy, but the second is tricky.

Identify Even Integers

This is pretty straight forward. A long time ago, I thought I invented this method. Turns out everyone's come to the same conclusion.

(x % 2 === 0) ? 'even' : 'odd';

This uses the modulo operator to figure out if there's anything left after dividing x by 2. If there is, it's odd.

Loop without Looping

The instinctual way to solve this problem is something like this.

var ints = [-3, -2, -1, 0, 1, 2, 3];

var getEvens = function (ints) {
  return ints.filter(function (x) {
    return x % 2 === 0;
  });
};

console.log(getEvens(ints)); // [ -2, 0, 2 ]

This uses the Array's filter method. It iterates through the Array and performs a callback. If the callback returns true, the item is included in the filtered Array.

If you look at the link, though, it's using a for loop. All the Array's iterator methods use loops; that's sort of the whole point of the Array data structure.

So, maybe we're thinking about this the wrong way. What is it we need to do? We need to run some code against every item in a collection.

Maybe we could do something like this.

var getEvens = function (ints) {
  var evens = [];

  if (ints[0] % 2 === 0) {
    evens.push(ints[0]);
  }

  if (ints[1] % 2 === 0) {
    evens.push(ints[1]);
  }

  ...

  return evens;
};

Technically, that would work as long as we copied that code enough times. It makes my teeth hurt to look at all that repetition, though. And what if the Array has 100,000 ints?

OK, scrap that.

How else can you get code to repeat without a loop? A function. That's the whole point of functions, right? They are reusable code.

var emergency = 0;

var getEvens = function (ints) {
  if (++emergency > ints.length) {
    throw new Error('whoah, too much recursion: ' + emergency);
  }

  return getEvens(ints);
};

There we go. We've got the code repeating and it's somewhat aware of the Array's length. We're on to something here.

Iterating with Recursion

Here's a better version with comments. Basically, we add an index parameter, combine it with a little tail recursion, and voilà! We're iterating an Array without technically using a loop. I'd argue that this is still a loop, but it's not one of the loop control flow statements.

var getEvens = function (ints, i) {
  var evens = [];

  // We added an optional index param.
  i = i || 0;

  // This keeps us out of an infinite loop.
  if (i < ints.length) {

    // Test the current item, include if it passes.
    if (ints[i] % 2 === 0) {
      evens.push(ints[i]);
    }

    // Move to the next item, concatenate result with this item.
    return evens.concat(getEvens(ints, i + 1));
  }

  // We've iterated too far, so stop the recursion
  // by returning the empty Array.  The concat in
  // the calling function will make it magically disappear!
  return evens;
};

var ints = [-3, -2, -1, 0, 1, 2, 3];

console.log(getEvens(ints));
// [ -2, 0, 2 ]

Performance

So, this achieves the objective spelled out by the problem. How does it perform, though?

Using the ints -5000 through 5000 in an Array, I tested this method and the filter version each 100 times. Here are the results.

Recursion Version
8388ms

Filter Version
148ms

Obviously, you want to use the filter version. Maybe we could refactor the recursion version to not use all those concats and speed it up, but it's not worth the effort. The first time I tested this I used an Array of 100,000 ints and - surprise! - the max callstack size was exceeded.