Flatten an array without recursion

Recursion is a process of re-doing the repititive subtasks, but in most cases it requires more memory than iteration.

Now without getting much into the theory of why recusrion is slower and why it causes the problem Maximum call stack size exceed. I will do a series of blog posts by solving real time problems, where we can remove recursion to write performant code.

I will make use of Javascript to write the solution, but the core idea will remain same for any programming language.

Flatten an array

Flatten an array is the most common task, which is commonly solved by making use of recursion. By removing the recursion, we can easily make it 28-33 times faster.

With Recursion

var list = [1, 2, 3, [[4]], [[[5]]], [6], [[7]]]

function flattenRecursive (list) {  
  var flatList = []
  list.forEach(function (item) {
    if (item instanceof Array === true) {
      flatList = flatList.concat(flattenRecursive(item))
    } else {
      flatList.push(item)
    }
  })
  return flatList
}

console.log(flattenRecursive(list))  

What's happening here?

We have an array with arbitrary nested values inside the it. We need to make it flat, so the end result should look like this.

[ 1, 2, 3, 4, 5, 6, 7 ]

We start with a forEach loop with a conditional block to re-run the same function again if the value inside an array itself is an array. We call it recursion.

Without Recursion

Update - @hypercubed has a valid concern over the mutable arrays. The below does not mutate the original array and instead creates a clone of it.

var list = [1, 2, 3, [[4]], [[[5]]], [6], [[7]]]

function flatten (list) {  
  var clonedList = list.slice(0)
  var flatList = []
  while (clonedList.length) {
    var item = clonedList.shift()
    if (item instanceof Array === true) {
      clonedList = item.concat(clonedList)
    } else {
      flatList.push(item)
    }
  }
  return flatList
}

Everything is same, but instead we have a while loop and a slightly different if block.

while loop runs until a conditional turns false. Here we pull the first item from the array using list.shift() and check to see if that itself is an array. if block will mutate the original list by concatenating pending items of an array.

Since we are removing the first element list.shift(), there will be a situation when list.length will become false and while loop will stop.

I did a quick benchmarking test using benchmark and results are quite impressive.

Results

flattenRecursive x 306,527 ops/sec ±1.37% (88 runs sampled)  
flatten x 428,224 ops/sec ±1.23% (91 runs sampled)  
Fastest is flatten  

You can check the final code on gist