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?

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));