CODEWITHSUNDEEP
javascriptrecursioncountreturn-value
Evan Fralin
Evan Fralin

Reputation: 1

How to keep track of a count during recursion?

I am trying to write a function that counts the occurrence of a particular key in a nested object. In the first function below, I am initializing a counter as an argument parameter, but it won't keep track of the count after the function returns from a recursive episode. In other words, the function will call itself, go into recursion, correctly add 1 to the counter, but when it comes back, the one is gone.

I am new to javascript!

I ended up solving the problem by using a blank array instead of a count; that is, I first recursively collected all the keys of all the nested objects and then counted them. So my question is, why can I keep track of an array, but not a count?

//Code that does not work (keeping track of a count):

const countKeysInObj = function(obj, key, count = 0) {
    for (let prop in obj) {
        if (prop === key) {
            console.log("counting");
            count += 1;
        }
        if (typeof obj[prop] === 'object') {
            console.log("recursing");
            countKeysInObj(obj[prop], key, count);
        }
    }
    return count;
}
var testobj = { 'e': { 'x': 'y' }, 't': { 'r': { 'e': 'r' }, 'p': { 'y': 'r' } }, 'y': 'e' };
console.log(countKeysInObj(testobj, "e")) // return 1, should be 2;

Upvotes: 0

Views: 387

Answers (3)

Scott Sauyet
Scott Sauyet

Reputation: 50807

The reason that your code did not work and the answer from mklauser did is that JavaScript is a call-by-sharing language. If it were call-by-reference, then what you tried would work. But when you change the value of count inside the function body, it does not update the reference in it's (recursive) parent's function body.

You could simulate something like call-by-reference, using a variant like this:

const countKeysInObj = function(obj, key, ref = {count: 0}) {
//                                        ^^^^^^^^^^^^^^^^
    for (let prop in obj) {
        if (prop === key) {
            console.log("counting");
            ref .count += 1;
        }
        if (typeof obj[prop] === 'object') {
            console.log("recursing");
            countKeysInObj(obj[prop], key, ref);
            //                             ^^^            
        }
    }
    return ref .count;
    //     ^^^^^^^^^^    
}

var testobj = { 'e': { 'x': 'y' }, 't': { 'r': { 'e': 'r' }, 'p': { 'y': 'r' } }, 'y': 'e' };
console.log(countKeysInObj(testobj, "e"))
var testobj = { 'e': { 'x': 'y' }, 't': { 'r': { 'e': 'r' }, 'p': { 'y': 'r' } }, 'y': 'e' };
console.log(countKeysInObj(testobj, "e"))

But I would personally prefer a more functional approach, something like this:

const countKeysInObj = (obj, key) => Object (obj) === obj
  ? Object .entries (obj) .reduce (
      (t, [k, v]) => t + (k == key ? 1 : 0) + countKeysInObj (v, key)
    , 0)
  : 0

var testobj = { 'e': { 'x': 'y' }, 't': { 'r': { 'e': 'r' }, 'p': { 'y': 'r' } }, 'y': 'e' };
console.log(countKeysInObj(testobj, "e"))

Upvotes: 0

danh
danh

Reputation: 62676

The call stack keeps track of return values for you.

Consider that the recursive definition of counting the keys is "the count at the current level plus the count resulting from the recursion".

const countKeysInObj = function(obj, key) {
  let count = 0;
  if (typeof obj === 'object')
    for (let prop in obj) {
      // for each key, the count is 1 if that key is the target plus the recursive result
      count += (prop === key ? 1 : 0) + countKeysInObj(obj[prop], key)
    }
  return count;
}

var testobj = { 'e': { 'x': 'y' }, 't': { 'r': { 'e': 'r' }, 'p': { 'y': 'r' } }, 'y': 'e' };
console.log(countKeysInObj(testobj, "e")) // 2;

Upvotes: 1

mklauser
mklauser

Reputation: 21

Try to use the retuned value and set the count variable from the returned recursed function.

const countKeysInObj = function(obj, key, count = 0) {
    for (let prop in obj) {
        if (prop === key) {
            console.log("counting");
            count += 1;
        }
        if (typeof obj[prop] === 'object') {
            console.log("recursing");
            count = countKeysInObj(obj[prop], key, count); // set count here.
        }
    }
    return count;
}

Upvotes: 1

Related Questions