Array.reduce and recursion

Question

I am trying to nest a recursive function in an Array.reduce call.

But the following does not work for the third instance only

const i1 = {'local': [['a','b']]};
const i2 = {'local': [['c','d']], 'recursive': []};
const i3 = {'local': [['c','d']], 'recursive': [{'local': [['e','f']]}]};

function reduce(current, result = []) {

    if(current.hasOwnProperty('local'))
       result.push(...current.local);

    if(current.hasOwnProperty('recursive'))
       result = current.recursive.reduce(reduce, result);
    //'result =' should be optional, but yields a wrong answer anyway

    return result;    
}

console.log(reduce(i1));
console.log(reduce(i2));
console.log(reduce(i3));

So instead of calling reduce I tried the following loop

for(var i = 0; i < current.recursive.length; ++i)
    result = reduce(current.recursive[i], result);
 //'result = ' is optional for it is passed by reference

and it works. Being new to JavaScript, I am certain of missing a key feature here, so could you explain ?

Output for the third instance should be

[ [ 'c', 'd' ], [ 'e', 'f' ] ]

but is

{ local: [ [ 'e', 'f' ] ] }

or

[ [ 'c', 'd' ] ]

when result = is removed.

why do you use Array#reduce? why do you need a recursion? the data base is not the same and the signature of Array#reduce needs the second parameter for the element. — Nina Scholz
– Nina Scholz, Commented Aug 15, 2019 at 17:24
You've made your code extra confusing by combining manual recursion with Array#reduce, mixing assignments and functional style, and naming your own function reduce. But I think the main issue is that your order of arguments is wrong. It should be function reduce(result, current). — melpomene
– melpomene, Commented Aug 15, 2019 at 17:28
The callback to array reduce takes the accumulator first and the element second. — Bergi
– Bergi, Commented Aug 15, 2019 at 17:32

Titus · Accepted Answer · 2019-08-15 17:31:58Z

2

The problem is the order of the parameters, the first argument to the reduce callback function is the accumulator not the current value. Try this:

const i1 = {'local': [['a','b']]};
const i2 = {'local': [['c','d']], 'recursive': []};
const i3 = {'local': [['c','d']], 'recursive': [{'local': [['e','f']]}]};

function reduce(result, current) {

    if(current.hasOwnProperty('local'))
       result.push(...current.local);

    if(current.hasOwnProperty('recursive'))
       result = current.recursive.reduce(reduce, result);
    //'result =' should be optional, but yields a wrong answer anyway

    return result;    
}

console.log(reduce([], i1));
console.log(reduce([], i2));
console.log(reduce([], i3));

answered Aug 15, 2019 at 17:31

Titus

22.6k1 gold badge26 silver badges36 bronze badges

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

2 Comments

3limin4t0r Over a year ago

You could also make the first argument optional, allowing you to simply call reduce(i1). Add if (current === undefined) { current = result; result = []; } to the start of the reduce function.

Titus Over a year ago

@3limin4t0r I'm sure the OP will change this to fit his needs, I just wanted show what the problem is.

Mulan · Accepted Answer · 2019-08-15 21:04:17Z

I think what you want to implement is flatten - It's no coincidence that it's a simple wrapper for Array.prototype.flatMap -

const i1 =
  { local: [[1,2]] }

const i2 = 
  { local: [[3,4]], recursive: [] }

const i3 =
  { local: [[3,4]], recursive: [{ local: [[5,6]] }] }

const i4 =
  { local: [[1,2]],
    recursive: [
      { local: [[3,4]] },
      { local: [[5,6]] , recursive: [{ local: [[7,8]] }] }] }

const flatten = ({ local = [], recursive = [] }) =>
  [ ...local, ...recursive.flatMap(flatten) ]

console.log(flatten(i1))
// [ [ 1, 2 ] ]

console.log(flatten(i2))
// [ [ 3, 4 ] ]

console.log(flatten(i3))
// [ [ 3, 4 ], [ 5, 6 ] ]

console.log(flatten(i4))
// [ [ 1, 2 ], [ 3, 4 ], [ 5, 6 ], [ 7, 8 ] ]

The spread arguments can be traded for Array.prototype.concat, if that is preferred -

const flatten = ({ local = [], recursive = [] }) =>
  [ ...local, ...recursive.flatMap(flatten) ]
  local.concat(recursive.flatMap(flatten))

Array.prototype.flatMap is a special kind of Array.prototype.reduce -

const flatten = ({ local = [], recursive = [] }) =>
  local.concat(
    recursive.reduce((r, x) => r.concat(flatten(x)), [])
  )

And since Array.prototype.concat is a pure operation, we can simplify it a bit more -

const flatten = ({ local = [], recursive = [] }) =>
  recursive.reduce((r, x) => r.concat(flatten(x)), local)

And finally we see it again using reduce and array spread arguments -

const flatten = ({ local = [], recursive = [] }) =>
  recursive.reduce((r, x) => [...r, ...flatten(x)], local)

Each of these flatten produce the exact same outputs and the input arrays are not mutated in the process. Hopefully this gives you a little insight on how the helpful Array.prototype.flatMap works.

Mohrn · Accepted Answer · 2019-08-15 17:57:47Z

This only covers the cases when local and recursive only includes one element, like in your example.

const i1 = { local: [["a", "b"]] };
const i2 = { local: [["c", "d"]], recursive: [] };
const i3 = { local: [["c", "d"]], recursive: [{ local: [["e", "f"]] }] };
const i4 = {
  local: [["c", "d"]],
  recursive: [{ local: [["e", "f"]], recursive: [{ local: [["g", "h"]] }] }]
};

const solution = ({ local: [firstItem], recursive }) =>
  [firstItem].concat(
    recursive && recursive.length ? solution(recursive[0]) : []
  );

console.log(solution(i1));
console.log(solution(i2));
console.log(solution(i3));
console.log(solution(i4));

local and recursive are arrays so it makes sense to me to append all children, not just the first, firstItem and recursive[0]

Collectives™ on Stack Overflow

Array.reduce and recursion

3 Answers 3

2 Comments

1 Comment

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

1 Comment

1 Comment

Related