Flatten nested arrays using recursion (and without using loops)

Question

My logic for the problem, using the below as the input.

var input = [['A','B'],1,2,3,['C','D']]

1. Check first element to see if is an Array or not using Array.isArray(input)
2. If first element is array, call function, first element ['A,'B'] as argument.
3. The first element of the nested array is 'A' which is not an array, so push this element into a result array, and shift this element out. Repeat the function call.

When trying to flatten nested arrays using recursion, my input variable to the function keeps getting reassigned, preventing me from calling the function again using the original array. How do I prevent the original input variable from getting reassigned?

I understand this is not the complete solution, however I am stuck at when I shift the first element out of the nested array.

I've gone through step by step with this function, but there must be something I'm missing, another set of eyes would help greatly.

I've also been using my chrome developer tool, set breakpoints to monitor the function step by step.

//Defining original input variable
var input = [['A','B'],1,2,3,['C','D']]
function flat(array){
 var result = []
 var firstElement = array[0]
//CHECK IF FIRST ELEMENT IS ARRAY OR NOT
 if(Array.isArray(firstElement)){
 return flat(firstElement) 
 } 
//IF ELEMENT NOT ARRAY, PUSH ELEMENT TO RESULT
 else{result.push(firstElement)
 array.shift() //removing child element
 return (flat(array)) //call function on same array
 }
if(array.length===0){return result}
}

First iteration: firstElement = ['A','B'], Array.isArray(firstElement) would be true, hence call flat(firstElement)

Second Iteration: firstElement = 'A', Array.isArray(firstElement) is false, so we 1. jump down to push this element into result 2. remove 'A' by using array.shift() 3. Call flat(array), where array is now ['B']

Third Iteration: firstElement = 'B', Array.isArray(firstElement) is false 1. jump down to push this element into result, result is now only ['B'] since I've reset the result when I recalled the function. 2. remove 'B' by using array.shift(), array is now empty, ->[ ] 3. How can I step out, and use flat() on the original input array?

• Christian Vincenzo Traina: Why? Just why? This is a purely didactic exercise, you won't ever need something like this in real life
• pishpish: @CristianTraìna It is an excellent exercise to get a grasp on recursion.
• samplecode3300: @CristianTraìna - Glad to know I won't be using this in real life haha. I could have easily done this using loops, but I'm trying to brush up on my recursion skills. It's still shaky. This was just one of the practice problems.
• Mark: It’s a good excercise. And useful in real life as soon as the nested arrays can also include more nested arrays like a tree.

Answer 1

Your code doesn't consider the following elements if the first element is an array. The solution below uses array.concat(...) to combine both the result of the recursion (going down the tree), but also to combine the results of processing the rest of the list (in the same level). Visualizing the problem as a tree, often helps with recursions IMO:

 [] 1 2 3 []
 | |
A [] C D
 |
 B C

So perhaps it is more clear here, that we must both concat the result of the recursion and the result of taking a "step" to the right (recursion again) which would otherwise be a loop iterating the array.

var input = [['A',['B', 'C']],1,2,3,['C','D']]
function flat(array) {
 var result = []
 if (array.length == 0) return result;
 
 if (Array.isArray(array[0])) {
 result = result.concat(flat(array[0])); // Step down
 } else {
 result.push(array[0]);
 }
 result = result.concat(flat(array.slice(1))) // Step right
 return result;
}
console.log(flat(input));
// ["A", "B", "C", 1, 2, 3, "C", "D"]

This is somewhat analogous to a version with loops:

function flat(array) {
 var result = []
 for (var i = 0; i < array.length; i++) {
 if (Array.isArray(array[i])) {
 result = result.concat(flat(array[i]));
 } else {
 result.push(array[i]);
 }
 }
 return result;
}

EDIT: For debugging purposes, you can track the depth to help get an overview of what happens where:

var input = [['A',['B', 'C']],1,2,3,['C','D']]
function flat(array, depth) {
 var result = []
 if (array.length == 0) return result;
 if (Array.isArray(array[0])) {
 result = result.concat(flat(array[0], depth + 1));
 } else {
 result.push(array[0]);
 }
 var res1 = flat(array.slice(1), depth);
 console.log("Depth: " + depth + " | Concatenating: [" + result + "] with: [" + res1 + "]");
 result = result.concat(res1)
 return result;
}
console.log(flat(input, 0));

• samplecode3300: have a clarifying question but first, thanks so much, your first solution I was trying to write. First iteration the second last line flat(array.slice(1)) , here array is the original input var input = [['A',['B', 'C']],1,2,3,['C','D']] Second Iteration , flat(array.slice(1)) is ['A',['B','C']], then we slice out 'A' Third Iteration, flat(array.slice(1)) is ['B','C'], up until array.length===0 How did we climb back out of the nested arrays to the point where when we call flat(array.slice(1)), the array is actually referring to our original input?
• samplecode3300: It has something to do with the call stack returning the "result" values right? Apologies for the long winded follow up. I've been using the Pythontutor visualizer for this, I think I'll just need to go over it more slowly.
• pishpish: @MaxHsu The "climbing out" is made implicitly by the function call stack. Take a piece of paper and try to follow things around.
• pishpish: @MaxHsu Oh, and .slice(1) leaves you with the same array as yours was after calling .shift() on it.
• Jeppe: @MaxHsu I have added a code-snippet which outputs a little more information. array.slice(1) returns array from index 1 (so excluding the first element). In the first iteration, that means 1,2,3,['C','D']] - which corresponds to the "rest" of the top-level in the tree in my post. So eventually, the recursion comes back to the top-left element and is returned.

Answer 2

If you want to avoid loops, and I'm considering concating/spreading arrays as loops, you need to pass the result array to your function.

const input = [['A', 'B'], 1, 2, 3, ['C', 'D']]
// Start the function with an empty result array.
function flat(array, result = []) {
 if (!array.length)
 return result
 // Extract first element.
 const first = array.shift()
 // Call the function with the array element and result array.
 if (Array.isArray(first))
 flat(first, result)
 // Or add the non array element.
 else
 result.push(first)
 // Call the function with the rest of the array and result array.
 flat(array, result)
 return result
}
console.log(flat(input))

• samplecode3300: @destroyer - Thanks for this one. I was reluctant to use a second argument since I was insistent on trying to understand my first attempt. However your solution I was able to grasp much more intuitively. Appreciate this solution!

Answer 3

Here is my answer if you are using JavaScript

You can use the below one line code to flatten n level nested Array

let flattendArray = input.flat(Infinity);

Or use this approach using reduce and concat

function flatDeep(arr, d = 1) {
 return d > 0 ? arr.reduce((acc, val) => acc.concat(Array.isArray(val) ? flatDeep(val, d - 1) : val), [])
 : arr.slice();
};

Refer this link