JavaScript — flatten an Array recursively
Flatten a dimensional array is a perfect problem to use recursion.
Recursion is great if you want to solve a big problem by solving smaller instances of that big problem.
Array we want to flatten
var arr = [1, [2, 3], [[4]]];The output should be
var arr = [1, 2, 3, 4]There are two main requirements of a recursive function:
A Stop Condition — the function returns a value when a certain condition is satisfied, without a further recursive call.
The Recursive Call — the function calls itself with an input which is a step closer to the stop condition.
For our problem, we are going to
1. check every index of the array
2. if typeof array index is Array
3. recursion call to flatten
4. else
5. push to a new array
The first step would be to create a function and call it.
We will call the function and pass the first index (which is 0) and the array we want to flatten.
Next, we will create a stop condition. The stop condition is once we reach the end of the array — meaning no index left to check.
While we haven’t reached to the end of the array, make a recursive call to the function with the next index.
Now we need to implement some logic. We need to check if the current array index as an Array. If it is, make a recursive call with this array. else, (the array index is not an array) push it to a new data structure (a new Array).
We have a working solution for our problem.
But What Actually happens when you flatten an array using recursion?
This is a great question. And to fully understand the code above, we need to understand what is going on when we are making recursive calls.
First, let’s refresh our mind with what happens when you call a function.
Basically, every time we call a function, a new stack frame is being created and all the functions data (return address, input parameter, local variables, register savings) get pushed into it. Then, this stack frame get pushed into the program stack. The program stack will execute the program (i.e the function) that it is on top of the stack. (we also maintain a stack pointer that points the stack frame that is on the top of the program stack).
The top stack frame will stay at the top until it will get resolved, meaning the function reaches its end.
Back to our recursive function
A recursive function is a function, that calls another function that calls another function and so on until we end it (get to our stop condition). And as we mentioned before, everytime a function is being called it creates a new program in the program stack. Calling a function without stopping can cause a stack over flow (hence the term/name stack overflow).
In our example, a function is being called first time, and then every time we reach to an index in the array which is an array. So having an array with 2 sub arrays, we will execute 3 different function calls. The first one and then 2 for each sub array.
Let’s see what happens when we run our example
Step 1: we create 2 global variables (global variables staying in the program stack as long as the program keeps running whereas local variables staying in the program stack as long as their function keeps running).
Anyway, our stack looks something like that
Step 2: we call the function flattenArray(0, [1, [2, 3], [[4]]]) so we are adding the function call to the stack
The function will loop through the array and if the current array index is not an array, its value will get pushed into the newArr variable. If current array index is an array, we will call the same function with new arguments.
Step 3: first loop, index 0 of the arr is not an array, therefore it gets pushed to the newArr . We increment the index to check by 1.
Step 4: second loop, index 1 is an Array, therefore we call the flattenArray function with index 0 and the current index value (which is an array). flattenArray(0, [2, 3])
Now our stack looks like this
Step 5: once again, we loop through the array. This time none of the index values is an array, so we simply push each value to the newArr . On the third loop we reach to the stop condition code
if(index == array.length) return false;
since our index is 2, and the array.length is also 2, we reach to the end of the array and return a result (a false result). Now our stack knows that the current program (function) is ended (a function gets resolved once it reaches a return statement or closing }), it will take it out of the stack and gets back to the program (function) before it.
Step 6: we are back to the original function, we increment the index to check by 1 and this time we call the function with the index 2. Index 2 is also an array so we call the flattenArray with the current index value and index 0. flattenArray(0, [[4]])
Looping on the current array, its index 0 is also an array so we once again calling flattenArray with the current index value and index 0. flattenArray(0, [4])
Looping on the current array, its index 0 is not an array so we push its value to the newArr , reach the stop condition (we reach to the end of the array) and return false result. The top program (function) on the stack getting resolved and we are back to the previous program (function)
Step 7: We increment the index to check by 1 so now we check index 1 of the [[4]]array, we reach to our stop condition code and find out that we are at the end of the current array, we return a false result and removing the top function from the stack.
Step 8: now we are back to the original array, we increment the index to check by 1 and want to keep looping the array but same as step 7, we reach the stop condition, find out we are at the end of the array, return a false result and removing the top function from the stack.
Step 8: we are back to where we start from. Our global program is now ending (since we are not doing anything else) and our new array newArr holds our flatten array result.
What’s the drawback of recursion??
Recursion uses more memory. Because the function has to add to the stack with each recursive call and keep the values there until the call is finished, the memory allocation is greater than that of an iterative function. also, recursion can be slow.
This problem affects our example since the array we try to flatten can be really deep nested and create a lot of function in the stack and use a lot of memory.
Can you do it without using recursion?
Yes.
Also can you do it without using another Array?
Yes.
Both of these questions try to see if we can solve this problem and flatten the array without allocating an extra space.
If we want to modify an existing data structure but don’t want to use extra space, we must modify it in-place
To do this, we can take advantage of the ... spread operator and the splice() method JS has to offer.
When the ... spread operator is used in the function call, it ‘expands’ an iterable object (i.e array) into the list of arguments. The spread syntax “spreads” the array into separate arguments.
The splice() method changes the contents of an array by removing or replacing existing elements and/or adding new elements in place.
Combining both options to array.splice(i, 1, …array[i]); we basically saying: Hey JS, please replace 1 item in the index i with the expanded/spreader arguments from the given array[i] . It will result with having a list of arguments (the array separate arguments) to replace the value at index i .
The tricky part here is to increment the i counter only if the array index value is not an Array.
