Convert recursive function to while loop

Question

I have a potential stack overflow issue with a recursive function. Usually I can solve this with a while loop and a condition, but I cannot figure out the condition to based this while loop on.

Here is the current recursive function which counts the number of handlers in an object of unknown # of nested objects.

countHandlers(obj){
    let count = 0;
    for(let k in obj){
        if(k === "_handlers"){
            count += obj[k].length;
        }
        else if(typeof obj[k] === 'object') {
            count += this.countHandlers(obj[k])
        }
    }
    return count;
}

Can this be converted to a non-recursive function?

I'd tend to think the problem is that you have a circular relationship somewhere, since you'd have to have a massively deep object to run into a stack overflow with that function. If the problem is indeed a circular relationship, you can keep your recursive function but just handle the circular relationship by not following an object a second time, using a Set to remember the ones you've already seen. — T.J. Crowder
– T.J. Crowder, Commented Sep 15, 2019 at 17:00
that's a good point. you'd need like thousands of nested objects for a stack overflow to occur. — user6713871
– user6713871, Commented Sep 15, 2019 at 17:08

Merkle Groot · Accepted Answer · 2019-09-15 17:03:01Z

4

The way I usually get around recursive functions is to use a stack or a queue to maintain the data that needs to be processed. Stacks are easier in JavaScript, so we'll go with that. :)

function countHandlers(obj) {
    let stack = [];
    stack.push(obj);

    let count = 0;
    while (stack.length > 0) {
        let currentObj = stack.pop();   

        for (let k in currentObj) {
            if (k === "_handlers") {
                count += currentObj[k].length;
            }
            else if (typeof currentObj[k] === 'object') {
                stack.push(currentObj[k]);
            }
        }
    }

    return count;
}

answered Sep 15, 2019 at 17:03

Merkle Groot

9565 silver badges10 bronze badges

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

5 Comments

T.J. Crowder Over a year ago

Yup, very simple in this case since the order in which the objects are visited isn't important. Nice.

georg Over a year ago

Queues are just as easy, simply replace .pop with .shift to go breadth-first.

Ry- Over a year ago

@georg: shift is O(n) on the size of the array, so that could be really inefficient.

georg Over a year ago

@Ry: that's true.

Merkle Groot Over a year ago

Somehow, I'd never used .shift() before. Thanks for that. Although this particular problem lends itself to "depth-first", I usually prefer a "breadth-first" approach.

Karl Stephen · Accepted Answer · 2019-09-15 17:31:19Z

Problem arises in such recursive function when you have circular reference. You have to keep track of what objects you already parsed.

Let's say we have this object :

var test = {
    _handlers: {
        length: 1
    }, 
    child1: {
        member1: {
            _handlers: [7, 9, 12], 
            child: {
                morehandlers: {
                    _handlers: {
                        length: 7
                    }
                }, 
                _handlers: [1]
            }
        }, 
        member2: {
            _handlers: {
                length: 1
            }
        }
    }, 
    child2: {
        value: 2
    }, 
    child3: {
        last: {
            _handlers: {
                length: 7
            }
        }
    }
}

Total handlers count should be 20.

And then we add a circular reference :

test.child1.member3 = test;

Here is how I would handle it without thinking of performances :

let parsedHandlers = null;
let handlersCountLaunched = false;
function countHandlers(obj) { // Cannot be async
    let countObj = obj;
    let count = 0;
    for (let i = 0; i < parsedHandlers.length; i++) {
        if (countObj === parsedHandlers[i]) {
            countObj = null;
            break;
        }
    }
    if (countObj !== null) {
        parsedHandlers.push(countObj);
        for (let k in obj) {
            if (k === "_handlers") {
                count += obj[k].length;
            } else if (typeof obj[k] === 'object') {
                count += this.countHandlers(obj[k]);
            }
        }
    }
    return count;
}
function getHandlersCount(mainObj) {
    if (!handlersCountLaunched) {
        parsedHandlers = [];
        handlersCountLaunched = true;
        let count = countHandlers(mainObj);
        handlersCountLaunched = false;
        parsedHandlers = null;
        return count;
    } else {
        console.error('TimingError : getHandlersCount() has been called and has not yet finished counting');
        return -1;
    }
}

console.log(getHandlersCount(test));

In javascript, unless you have setup a mapping logic, you can't retrive the parent object of a member. With a circular reference in the object, you will probably end up with the total amount of handlers in the object tree, unless you select a branch with no circular reference.

Circular references might not be part of the problem at hand. If they are, this isn’t a good way to check for them (O(n²) on the number of objects, which is significant if stack overflows are already an issue).

Collectives™ on Stack Overflow

Convert recursive function to while loop

2 Answers 2

5 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related