Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Recursive function inside of a loop

Tags:

javascript

I've been studying recursive functions and I'm starting to understand them more or less. I was working on a free code camp challenge when I came across this and I do not understand it. A recursive function inside of a for loop:

function steamroller(arr) {
   var newArr = [];

    for (var i = 0; i < arr.length; i++) {
       //If (i)th element is an array
       if (Array.isArray(arr[i])) {
          newArr = newArr.concat(steamroller(arr[i]));
          console.log(newArr);
       } else {
          newArr.push(arr[i]);
       }
   }
   return newArr;
}
steamroller([1, [2],[3, [[4]]]]);
//returns [1, 2, 3, 4]

The line I'm having a hard time understanding is:

newArr = newArr.concat(steamroller(arr[i]));

On that line, newArr is concatenated to what? The function is called again inside of the .concat method, right? But what happens to that for loop? Does the function call inside of the concat method force the loop to exit?

Here is a JSFiddle, I have each newArr logged to console, but I can't even follow it. The array is built up like so:

[1, 2]
[4]
[3, 4]
[1, 2, 3, 4] //Final

Thanks.

like image 494
Chirpizard Avatar asked Dec 04 '15 21:12

Chirpizard


1 Answers

The steamroller function needs to loop over the indices in the array provided as the function parameter in order to ensure each index of the array is seen.

However, the original array has a number of indices, which in turn may contain multiple indices themselves, all of which need to be looped over in turn.

The call to concat is done only on the current index of the loop, meaning that the outcome is the "steamrollered" representation of the current index.

Step by step

  1. The original array is passed in to the function: [1, [2],[3, [[4]]]]
  2. The loop begins with the first index: 1, which is not an array, so it is pushed to the resulting array.
  3. The next loop iteration's index is [2], which is an array, so is recursed.
  4. The first recursive call to the function receives [2] and iterates over it.
  5. The first iteration of this recursive call finds the index to be 2, which is not an array, so is pushed to the resulting array.
  6. ... continue ...

What we see is that as the nested arrays are iterated over using the recursive function, we always end up obtaining the internal integer values, no matter how nested.

like image 146
Greg Avatar answered Oct 06 '22 01:10

Greg