Nested object recursion trouble

Question

I am trying to write a recursive function that will check each nested object for an even number and return a final sum of those numbers. I am struggling to debug the function I have so far.

function nestedEvenSum(obj, sum = 0) {
  for(const k in obj) {
    if (obj[k].constructor === Object) {
      return sum += nestedEvenSum(obj[k], sum);
    }
    if (typeof obj[k] === "number" && obj[k] % 2 === 0) {
      sum += obj[k];
    }
    }
  return sum;
}

const obj = {
  a: 2,
  c: {c: {c: 2}, cc: 'b', ccc: 5},
  e: {e: {e: 2}, ee: 'car'}
}

console.log(nestedEvenSum(obj));

The function returns 8. It should return 6.

Also, I noticed that it forgets about object e completely, the last object called recursively is {c: 2}.

Just iterate ALL the object(s) recursively, counting into a "global" variable the total of the even numbers. — IT goldman, Jun 24 '22 at 16:47
You have to remove the `return` in `return sum += nestedEvenSum(obj[k], sum);` - otherwise it exits the parent early as soon as it encounters a child object. — Luatic, Jun 24 '22 at 16:50

ggorlen · Accepted Answer · 2022-06-24T17:10:42.140

This exhibits a classic recursion antipattern: passing the result (sum) down the call stack as a parameter while also trying to pass it up as a result, leading to a confused state of affairs and double-counting.

Here's a fundamental rule of thumb for recursion: data dependencies (the things used to compute a result) are the parameters, results are return values.

Make sum local to the frame, then accumulate on it during the frame, either because each element is a number (leaf node in the tree search) or it's a child that should be explored recursively. Don't return immediately in the loop or you will miss some of the children.

function nestedEvenSum(obj) {
  let sum = 0;

  for (const k in obj) {
    if (obj[k].constructor === Object) {
      sum += nestedEvenSum(obj[k]);
    }
    else if (typeof obj[k] === "number" && obj[k] % 2 === 0) {
      sum += obj[k];
    }
  }

  return sum;
}

const obj = {
  a: 2,
  c: {
    c: {
      c: 2
    },
    cc: 'b',
    ccc: 5
  },
  e: {
    e: {
      e: 2
    },
    ee: 'car'
  }
};

console.log(nestedEvenSum(obj));

Note that this algorithm ignores arrays.

Also note that the function's design is highly rigid due to the % 2 === 0 predicate. You might consider using a function that traverses any nested structure and returns an array or generator of results that can then be filtered, or a function that allows an arbitrary callback predicate to perform the filtering.

One exception to the one-way data flow rule is that sometimes you'll want to accumulate results onto a parameter array as an optimization rather than returning and merging multiple arrays as you move back up the call stack, but that doesn't apply here.

What throws me is the re-initialisation of `sum`. `sum` does not need to be passed again though right, recursively? — godhar, Jun 24 '22 at 19:09
No. `sum` is built per-frame and passed upward, not downward and upward as in your attempt. If you're stuck in a confused situation, stop and think about your data flow. If you have some data going both down and up, ask whether it's really necessary. 99% of the time, it's not--it's just overcomplicating the problem. Think about `sum` here as if you were a single call frame: what do I need to compute the sum? I need the sum of all my immediately available numbers, plus the sums of all of my child calls. The children don't care what the parents' sum is/was--it doesn't impact their calculation. — ggorlen, Jun 24 '22 at 21:22

Nina Scholz · Answer 2 · 2022-06-24T16:56:32.100

You need to remove the first return statement.

To get a shorter code, you could use conditional statements.

This approach does keep the sum of the actual object and does not hand over the sum to the nested level.

The handing over is only needed for tail call optimization (TCO) because of replacing the old function with the recursive funtion of the stack. Actuall TCO is in Javascript not widely supported ...

function nestedEvenSum(obj) {
    let sum = 0;
    for (const k in obj) {
        sum += obj[k] && typeof obj[k] === 'object'
            ? nestedEvenSum(obj[k])
            : obj[k] % 2 === 0
                ? obj[k]
                : 0;
    }
    return sum;
}

const obj = { a: 2, c: { c: { c: 2 }, cc: 'b', ccc: 5 }, e: { e: { e: 2 }, ee: 'car' } };

console.log(nestedEvenSum(obj));

score 1 · Answer 3 · answered Jun 24 '22 at 16:51

I think I figured it out.

First, you're returning if you find an object, which means you'll stop early, so I removed the early 'return'.

Second, you're double-counting if you find an object, because you're passing in the sum you already have and then adding it to the sum you already have.

Check this out, just a couple small changes:

function nestedEvenSum(obj, sum = 0) {
  for(const k in obj) {
    if (obj[k].constructor === Object) {
      sum = nestedEvenSum(obj[k], sum);
    }
    if (typeof obj[k] === "number" && obj[k] % 2 === 0) {
      sum += obj[k];
    }
  }
  return sum;
}

const obj = {
  a: 2,
  c: {c: {c: 2}, cc: 'b', ccc: 5},
  e: {e: {e: 2}, ee: 'car'}
}

console.log(nestedEvenSum(obj));

score 0 · Answer 4 · answered Jun 24 '22 at 22:14

Why not build this atop a simple deep filtering function?

const filterDeep = (p) => (o) =>
  p (o) ? [o] : Object (o) === o ? Object .values (o) .flatMap ((v) => filterDeep (p) (v)) : []
  
const sum = (ns) => ns .reduce ((a, b) => a + b, 0)

const nestedEvenSum = (o) => 
  sum (filterDeep (n => typeof n == 'number' && n % 2 == 0) (o))


const obj = {a: 2, c: {c: {c: 2}, cc: 'b', ccc: 5}, e: {e: {e: 2}, ee: 'car', j: [8, 6, 7, 5, 3, 0, 9]}}

console .log (nestedEvenSum (obj))

Here filterDeep accepts a predicate function and returns a function which takes an Object and collects all those (nested) elements which match that predicate. With a minor sum helper function, we can now write nestedEvenSum in a very simple manner and have useful helper functions available for other uses.

Nested object recursion trouble

4 Answers4