当前位置: 动力学知识库 > 问答 > 编程问答 >

javascript - Maximum call stack size exceeded. Can't figure out where logic is incorrect

问题描述:

I'm having trouble figuring out how to implement the contains method below. I'm trying to use depth first search to find if the tree contains a value, but I'm not sure what's wrong with my implementation.

class Tree {

constructor(val) {

this.value = val;

this.children = [];

}

addChild(val) {

this.children.push(new Tree(val));

}

contains(val) {

if (this.value === val) {

return true;

} else if (this.children.length > 0) {

for (var i = 0; i < this.children.length; i++) {

this.contains(this.children[i].contains(value));

}

// When it gets to the leaf node, how do I go back to the previous call?

// Do I need to return something here?

}

return false; // I may be incorrect on this, but it should return false (execute this line) only when every node has been visited, and there are no more nodes to check.

}

};

So when I do this:

const T = new Tree(100);

T.addChild(50);

T.addChild(40);

T.children[0].addChild(3);

console.log(T.contains(40));

I error out because of a maximum call stack error.

网友答案:

This line:

this.contains(this.children[i].contains(value));

is questionable because as contains should return a boolean, it doesn't make sense to then check again if the tree contains that boolean value. Also, the problem is on this line: you are calling contains with the exact same arguments (considering this as an argument) within itself, meaning it will never stop, resulting in a "maximum call stack size exceeded" error -- a.k.a. stack overflow.

Instead, you should change it to this:

if (this.children[i].contains(value))
    return true;

That way, the first time it finds the value, it returns. The recursion works as expected because it has a base case, i.e. either finding the value in this.children or falling off the end of the loop.

分享给朋友:
您可能感兴趣的文章:
随机阅读: