Recursion issue using Javascript Issue

Question

I am working on this challenge from FreeCodeCamp

Flatten a nested array. You must account for varying levels of nesting.

I am trying to solve it using recursion.

Here is my code:

function steamroller(arr) {
    var flatArray = [];

    function flatten(obj) {
        if (!Array.isArray(obj)) {
            return(obj);
        }
        for (var i in obj) {
            return flatten(obj[i]);
        }
    }

    flatArray.push(flatten(arr));

    console.log(flatArray);
}

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

This logs:

Array [ 1 ]

I can see the problem, the return statement breaks the for loop so only the first value is returned.

However if I leave out the return and just use:

flatten(obj[i]);

I get back:

Array [ undefined ]

What should I do to fix this?

Don't use for ... in loops to iterate through arrays. Use .forEach() or a numeric index in an ordinary for loop. — Pointy
– Pointy, Commented Jul 23, 2015 at 4:13
You need to concatenate those results, rather than return each recursively flattened element (note after the first return the function will entirely return). — DanZimm
– DanZimm, Commented Jul 23, 2015 at 4:23
These all make sense, just learning JS so forEach is next! Extremely helpful replies and comments, especially the underscore.js one :D — John Behan
– John Behan, Commented Jul 23, 2015 at 8:01

CD.. · Accepted Answer · 2015-07-23 04:24:46Z

2

You need to add the items to the result array.

function flatten(arr){
  var flat = [];

  arr.forEach(function(item){     
    flat.push.apply(flat, Array.isArray(item) ? flatten(item) : [item]);      
  });

  return flat;
}

answered Jul 23, 2015 at 4:24

CD..

74.3k25 gold badges160 silver badges170 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Nina Satragno · Accepted Answer · 2015-07-23 04:27:16Z

1

I modified your code so that it works, adding comments:

function steamroller(arr) {
var flatArray = [];

function flatten(obj) {
    if (!Array.isArray(obj)) {
        // We got to the innermost element. Push it to the array.
        flatArray.push(obj); 
        return;
    }
    for (i = 0; i < obj.length; i++) {
        flatten(obj[i]); // Do not return here.
    }
}

flatten(arr);

console.log(flatArray);
}

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

answered Jul 23, 2015 at 4:27

Nina Satragno

6014 silver badges8 bronze badges

2 Comments

John Behan Over a year ago

thanks for this, I'm submitting this answer as it represents my current level with Javascript, is this a good approach in your opinion?

Nina Satragno Over a year ago

To be honest, CD..'s approach is cleaner as it only uses one function and has no side effects. If your code has to run on node or a modern browser it's probably the best one. Beware however that forEach does not work on older IE versions, so if you wanted complete compatibility you'd have to replace it with an old style for.

Carsten Massmann · Accepted Answer · 2015-07-23 05:44:07Z

Here is a slightly different approach:

function flat(a,f){
 if (!f) var f=[];
 a.forEach(function(e){
  if (Array.isArray(e)) flat(e,f);
  else f.push(e);
 });
 return f;
}

var flatArray=flat(deepArray);

The function returns the flattened array each time but ignores its return value in the inner calls of itself (flat(e,f)). Instead it keeps pushing each non-Array value to the same f-Array that was defined initially in the outer call of flat(a).

Using the second (usually unused) argument you can also concatenate values to an already existing flat array like

var a=[[2,4,[5,6,[7,8],[9,10]],1],3];
var fl1=flat(a);
// "2|4|5|6|7|8|9|10|1|3"
var fl2=flat(a,fl1);
// "2|4|5|6|7|8|9|10|1|3|2|4|5|6|7|8|9|10|1|3"

ThiagoSckianta · Accepted Answer · 2016-03-12 05:32:07Z

A fully recursive solution, if you don't need to keep the original array intact:

function flatten (obj, memo) {
    memo = (memo || []);
    if (Array.isArray(obj)) {
        if (obj.length) {
            // flatten the first element, removing it from the original array
            flatten(obj.shift(), memo);
            // flatten the rest of the original array
            flatten(obj, memo);
        }
        return memo;
    }
    return memo.push(obj);
}

We firstly check if obj is an array. Then, if it is not empty, flatten the first element, them flatten the rest. If object is not an array, it is returned and pushed into the memo array, wich is returned.

Notice that in the first line I'm setting memo = (memo || []). This makes sure we always get a new array in the first call, if memo is not set.

Luffy Liu · Accepted Answer · 2020-09-22 14:30:48Z

0

function steamrollArray(arr) {

  let string = String(arr);
  let strArr = string.split(",");
      
  for (let i in strArr){

    if (strArr[i]==""){
      strArr.splice(i,1); 
      
    }

    if (strArr[i]=="[object Object]"){
      strArr[i] = {}; 
    }

    if (isNaN(parseInt(strArr[i],10))== false){
      strArr[i] = parseInt(strArr[i]); 
    }

  }

  return strArr;

}

answered Sep 22, 2020 at 14:30

Luffy Liu

1

1 Comment

drops Over a year ago

Hi, please add an explanation to what you changed

Scott Sauyet · Accepted Answer · 2020-09-23 21:14:38Z

Because this was recently brought back up with a new answer, perhaps it's time to revisit it.

This is a fairly simple recursive process. When this question was asked, ES5 was ubiquitous and ES6/ES2015 was being implemented everywhere.

A simple ES5 solution would look like this:

const flat = (ns) => 
  ns .map (n => Array .isArray (n) ? flat (n) : n)
     .reduce ((a, b) => a .concat (b), [])

but this pattern was made unnecessary by ES6, and that map-reduce(concat) pattern could now be written with Array.prototype.flatMap:

const flatter = (ns) => 
  ns .flatMap(n => Array .isArray (n) ? flatter (n) : n)

However, you don't even need to do this, because ES6 also introduced Array.prototype.flat, which allows us to write this:

const flattest = (ns) =>
  ns .flat (Infinity)

const flat = (ns) => 
  ns .map (n => Array .isArray (n) ? flat (n) : n)
     .reduce ((a, b) => a .concat (b), [])

const flatter = (ns) => 
  ns .flatMap(n => Array .isArray (n) ? flatter (n) : n)

const flattest = (ns) =>
  ns .flat (Infinity)


const data = [1, [2], [3, [[4]]]]

console .log (flat (data))
console .log (flatter (data))
console .log (flattest (data))

Collectives™ on Stack Overflow

Recursion issue using Javascript Issue

6 Answers 6

Comments

2 Comments

Comments

Comments

1 Comment

Comments

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

2 Comments

Comments

Comments

1 Comment

Comments

Related