재귀적 구조를 짤때 주의할 점(feat. Tree 타입구현)

이번에는 바보 같지만, 내가 자주 실수 하는 부분에 있어 잊지 않기 위해 포스팅을 한다. 

 

클래스 tree라는 것이 있고, 해당 구조는 아래와 같다고 하자. 

 

class Tree {

constructor(value) {

this.value = value;

this.children = [];

}

 

여기에서 value를 가지고 있는지 탐색을 할 수 있는

contains이라는 메소드를 만들고자 하면, 

 

contains(value){

    if(this.value === value) return true;

 

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

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

}

 

return false

}

 

로 하면 된다. 

굉장히 쉬워 보이지만, 파란색으로 표시된 내가 계속 틀렸던 부분에 대해 기록하고 자한다. 

 

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

이렇게 적으면, children을 재귀적으로 탐색하고, value가 같다면 return true할 줄알고 적었던 코딩이다.  하지만, 만약 this.value !==value인 경우에는 for문을 다 탐색하지 못하고 
return false해버리기 때문에 실패했다. 

 

2. return this.children[i].contains(value)

역시나, 이렇게 적었을때도, for문을 다 돌지 못하고, return false를 해버리는 경우가 발생하여,
실패했다.  어떤 결과가 나오게 되든 무조건 return 해버리기 때문에, for문을 탐색하지 못한다.

 

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

정답이다. false인 경우에는 i++하여 for문을 계속 돌게 되고 true인 경우에만
return true하게 되며, for문이 다 끝났음에도 return true하지 못하면 
최종적으로 return false 하게 된다.