Максимальный размер стека вызовов. Невозможно определить, где логика неверна

Question

У меня возникли проблемы с выяснением того, как реализовать метод contains ниже. Я пытаюсь использовать поиск глубины, чтобы найти, содержит ли дерево значение, но я не уверен, что случилось с моей реализацией.

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. 
    } 
}; 

Так что, когда я делаю это:

const T = new Tree(100); 
T.addChild(50); 
T.addChild(40); 
T.children[0].addChild(3); 

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

я ошибка из-за максимальной ошибки стека вызовов.

Answer 1

Эта линия:

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

сомнительна, потому что, как contains должна возвращать логическое значение, это не имеет смысла, чтобы затем снова проверьте, если дерево содержит это логическое значение. Кроме того, проблема заключается в этой строке: вы вызываете contains с теми же аргументами (с учетом в качестве аргумента) внутри себя, то есть он никогда не остановится, что приведет к ошибке «превышение максимального размера звонка» - иначе переполнение стека ,

Вместо этого, вы должны изменить его к этому:

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

Таким образом, в первый раз он находит значение, то оно возвращается. Рекурсия работает так, как ожидалось, потому что она имеет базовый футляр , то есть либо находить значение в this.children, либо падать с конца цикла.