5

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.

Improve this question
4
  • 3
    If the element of the arr is an Array, a recursive call is made on that array. So newArr is concatenated to what your recursive procedure returns on that element array (arr[i], for some i). Commented Dec 4, 2015 at 21:07
  • 2
    Seems like a rather convoluted way of implementing flatten... Am I missing something? Commented Dec 4, 2015 at 21:13
  • 1
    newArr.concat(steamroller(arr[i])); is concatinating newArr with steamroller(arr[i]) and returns a new array. this has to be assigned to a varibale for using. Commented Dec 4, 2015 at 21:14
  • 1
    @elclanrs Yeah, that is the point of the exercise, to "flatten" the array. As a student that is a new expression for me. Is there an easier way to do this? I'm not looking for easy answers, I prefer to actually learn. Commented Dec 4, 2015 at 21:49

5 Answers 5

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks. This helped tremendously!
1

It sounds like your mental muddling is mostly to do with the way "the stack" works.

A basic function call pauses execution at the point that it was called, and steps through each of the lines inside the function, then resumes outside of the function. And, you can have functions run inside of other functions; that much you may have already known.

The important thing to understand here is everything that the program is keeping track of. For starters, the program keeps track of what position it was being called from so it can "pop up one" in the stack, and continue. eg, at the midpoint of execution the stack may look like this (knowing which function/line it's at):

steamroller:10
steamroller:8
steamroller:8
main:20

Then its current loop hits "return"...

steamroller:8
steamroller:8
main:20

But that's not all - it also preserves each instance of the variables declared in that run of the function. You can, in fact, have about 5 or 6 or 5 million newArrs because those variables are declared on the stack, not in one singular spot.

And none of that information - the line number, or instance variables, are destroyed when it enters a function - it just saves its spot in the current function, and steps through the inner one.

Make sense?

Improve this answer

Comments

1

First enter:

steamroller([1, [2],[3, [[4]]]])

First element isn't an Array, so newArr receives '1'. Second element is an Array, so it calls steamroller again:

steamroller([1, [2],[3, [[4]]]])->steamroller(2)

It's not an array, so it will concat the element to a newArr, so it will simply concat 2 to an empty array. The function will return it, and concat the [2] to the newArr that contains [1], and now you have [1,2], and the console pops out the first line you saw on your fiddle.

I think you got it to what happens latter, but comment you still need explanation for what happens with 3 and 4.

Improve this answer

Comments

1

With recursive functions is that the return of the console will be a mess because is different than a normal loop it need to finish the last position of the recursive tree before return all the values in the console, so if you put in one of the positions of the array with a more deeper position like [[[[3]]]] it will go to the end of the position and then it will return all the values, so if you put some kind of console to see how is working your recursive function you will receive some kind of tree, not like a normal loop, that's the danger with the recursive functions, and they can be pretty heavy to the memory speaking about CPU usage in a production server. so if you can perform this operation with doing any recursive function it will be better.

So if you change you code to

 steamroller([1, [2],[3, [4]]]);
 //the return will be
 [1, 2]
 [3, 4]
 [1, 2, 3, 4]

Speaking about levels in the recursive tree So if you put the [[3]] as the [[4]] the return will be in the same level of the tree.

 steamroller([1, [2],[[3], [4]]]);
 //the return will be
 [1, 2]
 [3]
 [4]
 [3, 4]
 [1, 2, 3, 4]

Hi hope that can get you a better idea about the recursive functions

Improve this answer

1 Comment

Thanks, Felipe, this does help. Your first sentence helps a lot, I understand now why the console.log looks so different since it is logging from two different instances of the function; the first call, and then the recursive call... I think! :-) Thanks for the answer!
0

If we inspect the run without the recursion then:

i = 0 => arr[i] = 1 => newArr.push(arr[i]) => newArr = [1]
i = 1 => arr[i] = [2] => steamroller(arr[i]) = [2] => newArr = [1, 2]
i = 2 => arr[i] = [3, [[4]]] => steamroller(arr[i]) = [3, 4] => newArr = [1, 2, 3, 4]
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.