Recursive function inside a loop

I study recursive functions, and I begin to understand them more or less. When I came across this, I was working on the problem of free code camp, and I do not understand. A recursive function inside 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 with which I can hardly understand:

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

In this line, newArr combined with what? The function is called again inside the .concat method, right? But what happens to the loop? Does calling a function inside the concat method loop to exit?

Here is the JSFiddle , I have every newArr connected to the console, but I can’t even trace it. An array is created like this:

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

Thanks.

+5
source share
5 answers

The steamroller function must loop the indexes in the array provided as a parameter to the function to ensure that each index of the array is viewed.

However, the source array has several indices, which, in turn, can contain several indices at once, all of which must be looped in turn.

The concat call is only performed on the current loop index, which means that the result is a "frame" representation of the current index.

Step by step

  • The original array is passed to the function: [1, [2],[3, [[4]]]]
  • The loop begins with the first index: 1 , which is not an array, so it is carried over to the resulting array.
  • The next loop iteration index is [2] , which is an array, therefore recursive.
  • The first recursive function call gets [2] and iterates over it.
  • The first iteration of this recursive call finds index 2 , which is not an array, so it is transferred to the resulting array.
  • ... continue...

We see that since nested arrays are repeated using a recursive function, we always get the internal values ​​of an integer, regardless of how they are nested.

+5
source

First enter:

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

The first element is not an array, so newArr gets "1". The second element is an array, so it again calls the rink:

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

It is not an array, therefore it will be a concat element for newArr, therefore it will just be concat 2 for an empty array. The function will return it and add [2] to newArr, which contains [1], and now you have [1,2], and the console pops the first line that you saw in your violin.

I think you understand what happens last, but comment that you still need an explanation of what happens with 3 and 4.

+1
source

It seems that your mental confusion is mainly related to how the "stack" works.

The main function call pauses execution at the point at which it was called, and passes through each of the lines inside the function, then resumes work outside the function. And you can have functions performed inside other functions; what you might already know.

Important to understand here is everything that the program tracks. To begin with, the program keeps track of what position it called so that it can "pop up" on the stack and continue. for example, in the middle of the stack, it might look like this (knowing which function / builds it):

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

Then its current loop falls into "return" ...

 steamroller:8 steamroller:8 main:20 

But that’s not all - it also saves every instance of the variables declared in this function call. In fact, you can have about 5 or 6 or 5 million newArr , because these variables are declared on the stack, and not in one particular place.

And none of this data β€” line number or instance variables are destroyed when it enters a function β€” it simply saves its place in the current function and goes through the internal one.

Make sense?

+1
source

With recursive functions, it means that returning the console will be useless because it is different from the usual loop, it must end the last position of the recursive tree before returning all the values ​​in the console, so if you add one of the positions of the array with a deeper position like [[[[3]]]], it will move to the end of the position and then return all the values, so if you place some console to see how your recursive function works, you will get some kind of tree, and not like a regular cycle that is dangerous with recursive functions, and they can be quite hard for memory, talking about CPU usage on a production server. therefore, if you can perform this operation using any recursive function, it will be better.

So if you change the code to

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

Speaking of levels in a recursive tree, therefore, if you put [[3]] as [[4]], the return will be at 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, I hope you can better understand recursive functions.

+1
source

If we check the run without 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] 
0
source

Source: https://habr.com/ru/post/1237428/


All Articles