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

Question

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.

I'm guessing calling `contains()` twice inside a loop that is actually inside `contains()`, becomes too much for the poor browser — adeneo, Aug 12 '16 at 23:25

rvighne · Accepted Answer · 2016-08-12T23:35:46.677

3

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.

edited Aug 12 '16 at 23:35

answered Aug 12 '16 at 23:29

rvighne

20,755
11
51
73

@rvignhne could you explain what you mean by " 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." – TheRealFakeNews Aug 13 '16 at 00:38
@AlanH Since you're calling `contains` on `this`, you are not checking the next level down in the tree as you intended; instead, you are checking the same level of the tree for a boolean value (returned from the second contains call). If `children` does not contain booleans in it, `contains` will never find one -- but it will spawn unlimited copies of itself, each trying to find it, eventually resulting in a stack overflow. [This question](http://stackoverflow.com/questions/717725/understanding-recursion) has some good examples of recursion. – rvighne Aug 13 '16 at 01:30

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

1 Answers1