Flattening an array recursively (withoout looping) javascript

Question

I'm practicing recursion and am trying to flatten an array without looping (recursion only). As a first step I did the iterative approach and it worked, but am stuck on the pure recursion version:

function flattenRecursive(arr) {
    if (arr.length === 1) {
        return arr;
    }

    return Array.isArray(arr) ? arr = arr.concat(flattenRecursive(arr)) : flattenRecursive(arr.slice(1))
}

console.log(flattenRecursive([
    [2, 7],
    [8, 3],
    [1, 4], 7
])) //should return [2,7,8,3,1,4,7] but isn't - maximum call stack error


//working version (thanks @Dave!):

function flattenRecursive(arr) {
    if (arr.length === 1) {
        return arr;
    }

    return arr[0].concat(Array.isArray(arr) ? flattenRecursive(arr.slice(1)) : arr);
}

console.log(flattenRecursive([
    [2, 7],
    [8, 3],
    [1, 4], 7
]))

//returns [ 2, 7, 8, 3, 1, 4, 7 ]

`arr.concat(flattenRecursive(arr))` is causing the infinite recursion. — Ryan, Sep 10 '15 at 14:26
@charlietfl - it's true the first time you call the function, which then calls the function again with the same argument - `arr` - and hence will always be true. It never gets to the last item in the array. — Adam Jenkins, Sep 10 '15 at 14:38
Just curious why you want to do this recursively. It's trivial to do it if you don't want to do it in-place. Is this a thought exercise? — , Sep 10 '15 at 14:42
@torazaburo an exercise in solidfying my understanding of recursion (academic) :) how would you do this in place? — devdropper87, Sep 10 '15 at 14:44
See closely related question with in-place recursive solution: http://stackoverflow.com/questions/32491404/javascript-flatten-multidimensional-array-in-place-using-recursion/32518424#32518424. Another question which has a recursive answer is at http://stackoverflow.com/questions/29158723/javascipt-flattening-an-array-of-arrays-of-objects/29158887#29158887. By the way, do you expect the solution to work on nested arrays? Your accepted answer does not. — , Sep 11 '15 at 08:01

Dave · Accepted Answer · 2015-09-11T15:02:30.563

2

Here's a working version that's slightly less verbose.

//using reduce
function flattenRecursive(arr) {
  return arr.reduce(function(result, a){
    return result.concat(Array.isArray(a) ? flattenRecursive(a) : a);
  }, []);
}

//without reduce
function flattenRecursive2(arr) {
  if (arr.length === 0)
    return arr;

  var head = arr.shift();
  if (Array.isArray(head))
    return flattenRecursive2(head).concat(flattenRecursive2(arr));
  else
    return [head].concat(flattenRecursive2(arr));
}

var testArray = [1,[2, 3],[[4, 5, [6, 7]], [8, 9]], 10];
console.log(flattenRecursive(testArray));
console.log(flattenRecursive2(testArray));

<script src="http://gh-canon.github.io/stack-snippet-console/console.min.js"></script>

edited Sep 11 '15 at 15:02

answered Sep 10 '15 at 14:37

Dave

10,748
3
43
54

1

hey @dave that's awesome, but internally reduce uses each, which is essentially a for loop. I was messing around based on the solution you provided, and sometimes sh$t just works! updating my code above to the working solution, thanks for the inspiration! – devdropper87 Sep 10 '15 at 14:42
@devdropper87 - your recursive function fails if the first element in the array is not an array - e.g. `console.log(flattenRecursive([7, [2, 7], [8, 3], [1, 4], 7 ]))` – Adam Jenkins Sep 10 '15 at 15:20
1

I'm stumped, I tried to do an else if it's not an array but that's not working. what would you suggest? @dave any tips? – devdropper87 Sep 10 '15 at 17:00
@devdropper87 I added an alternative that doesn't use `.reduce()` – Dave Sep 10 '15 at 18:00
@torazaburo the second example is now fixed for all nested array cases. – Dave Sep 11 '15 at 15:04

score 1 · Answer 2 · edited Sep 11 '15 at 20:24

Sorry, I do not have the reputation to comment. Here are my 2 cents.

1) be careful about your initial condition. Here, it seems that if your input is ̀arr = [[1,2]], your function returns [[1,2]], while you would like it to return [1,2].

2) in the core of the recursion, you must be sure than you recursively call your function with a smaller argument. Here, you should concat the first element of your array with the flattened rest of the array. The functionslice` may be handy for that.

3) It would be also be possible to use a reduce-like function.

Flattening an array recursively (withoout looping) javascript

2 Answers2