Javascript - recursion/for loop for flattening array

Question

So, here is a sample solution to solve the problem of flattening an array. My question is not 'how' to flatten the array. Rather, I am trying to understand some underlying functionality occurring in this recursion.

This solution goes through each element of the original array, breaking down any elements that are arrays by putting them back through the function until they are no longer arrays and can be pushed to the new array.

My question is, how does the 'for' loop keep track of all of the times that an element is put back through the function, and also continue looping through the rest of the 'original' array that it is working on at the time? It must be keeping track somehow otherwise every time an element is an array and is put back through, the current loop would be cut short. Hope my question makes sense.

function steamrollArray(array) {
  var flatArray = [];

  flatten(array);

  function flatten(array) {
    for (var i = 0; i < array.length; i++) {
      if (Array.isArray(array[i])) {
        flatten(array[i]);
      } else {
        flatArray.push(array[i]);
      }
    }
  }

  return flatArray;
}
steamrollArray([1, [2], [3, [[4]]]]);

Answer 1

I think there will be better answers, but here goes...

At minimum, don't think of it as "breaking" the loop, think of it as continuing to execute code in a procedural order. So from inside the context of the loop, it calls itself as a function, when that function has completed, it continues in the loop. Example

var item = [1, [2, 3], 4]

The execution of flatten(item) would be:

Loop 1: 
  Push 1
Loop 2: 
  Start a call to flatten with [2, 3]
  Loop 1: 
    push 2
  Loop 2: 
    push 3
  End loop
Loop 3: 
  Push 4
End Loop.

So the point is, it is simply executing a procedure of steps. It's not having to "remember" where it was, when a function returns, javascript simply continues to process from where the function was called.

You may wish to review call stacks.

Answer 2

The result array flatArray is in the lexical closure of the helper function and thus the element that are not themselves arrays are pushed to this and the order of which they are put on the result is in the order they are iterated.

When one of the elements is an array it calls flatten(array[i]) which flattens the elements of that element before returning. As with all functions the execution of a statement needs to finish before the next statement can be done and calling a function does not cancel the current function at all. It resumes and continues until the end or a return statement.

Imagine this function:

function test () {
  console.log("hello, ");
  console.log("world!");
}

When this is called it does wait until the whole console.log("hello, ") has finished before doing statement two (console.log("world!")). If it would be recursive call that call needs to finish before doing statement two. It works the same for all function calls, noe only recursive ones.

Answer 3

It doesn't actually put elements 'back' through the function that only happens one time. It checks if an element is an array and then loops through that array.

If its not an array it pushes it to flatArray. The recursion here is that if any element is an array it goes through the flatten function. Then if that array has element that is an array THAT element is sent into flatten and so on and so on.

Lets take the following example: [1, [2], [3, [[4]]]]

we start looping->

• index 0 is 1 and not an array, so it is pushed to flatArray
• index 1 is an array and so we recurse - in that we have a 2 - which is then pushed
• index 2 is an array, so we recurse, index 0 of that inner array is a non array 3, so it is pushed. Then we have that last index - an array, which we recurse into, to find another array - recurse again - finally getting to the 4, which we push..

Answer 4

The 'keeping track' of each recursion step happens in the same way any other method call works; the javascript engine keeps track of the variables and scopes any time a new method is called in the call stack.

For your specific example, perhaps it will be easier to see what's happening when the flatten function is no longer nested.

function steamrollArray(array) {
  var flatArray = [];
  flatten(array, flatArray);
  return flatArray;
}

function flatten(array, flatArray) {
  flatArray = flatArray || [];

  for (var i = 0; i < array.length; i++) {
    if (Array.isArray(array[i])) {
      flatten(array[i]);
    } else {
      flatArray.push(array[i]);
    }
  }
}

steamrollArray([1, [2], [3, [[4]]]]); # [1, 2, 3, 4]

Some slight modifications were required as the flatArray variable is no longer accessible to the flatten function. But the mods make the steamrollArray seem superfluous... lets get rid of it.

function flatten(array, flatArray) {
  flatArray = flatArray || [];

  for (var i = 0; i < array.length; i++) {
    if (Array.isArray(array[i])) {
      flatten(array[i], flatArray);
    } else {
      flatArray.push(array[i]);
    }
  }

  return flatArray;
}

flatten([1, [2], [3, [[4]]]]);  # [1, 2, 3, 4]

Now it's a little more obvious where and how the recursion is happening. Any time an array is 'discovered', it too is flattened. Values are either pushed onto a new array, or pushed onto the the array passed as the second parameter. Each time flatten is called within the for loop, the array at position i is itself flattened and pushed onto the flatArray. As flatArray is also passed to the flatten function recursively, all the values will be collected into that array.

Answer 5

I have a simpler solution which works with any level of nesting in array.

function flattenArray(arr){

  for(var i=0;i<arr.length;i++){

    if(arr[i] instanceof Array){

      Array.prototype.splice.apply(arr,[i,1].concat(arr[i]))
       i--;
    }

  }

  return arr;
}

Answer 6

The solution of flattening array using the for-of loop along with 2 other way

Using for-of loop

let array = [1, [2], [3, [[4]]]];
let output = [];
let flattenArray = (arr) => {
  for(let a of arr) {
   Array.isArray(a) ? flattenArray(a) : output.push(a);
  }
  return output;
}
console.log(flattenArray(array));

Using reduce() method

let array = [1, [2], [3, [[4]]]]
function flattenArray(ary) {
 return ary.reduce((acc, val) => {
  if (Array.isArray(val)) {
   return acc.concat(flattenArray(val))
  }
   return acc.concat(val)
  },[])
}
console.log(flattenArray(array));

Using flat() method

let array = [1, [2], [3, [[4]]]];
let output = array.flat(Infinity); // use Infinity for flattening nested levels.
console.log(output);

Answer 7

let array = [1, [2], [3, [[4]]]];

const final = [];

const stack = [];

for (let i = 0; i < array.length; i++) {
  const ele = array[i];
  stack.push(ele);
  
  while (stack.length) {
    const first = stack.shift();
    if (Array.isArray(first)) {
      first.forEach(ele => stack.push(ele))
    } else {
      final.push(first)
    }
  }
}

console.log( final.join(', '));