재귀 함수 사용 시에 간과했던 실행 순서

Tree 자료구조를 구현 중에 있습니다.

 

해당 Tree는 value와 children 키를 가지고, 각각 숫자, 배열의 값을 할당했습니다.

 

Tree에 값은 추가했지만, 특정 값을 검색하는 것에서 애를 먹었습니다.

우선, 로직은 맞았다고 생각했는데, 이상하게, children의 0번째 인덱스만 검사를 하는 것이었습니다.

 

코드를 보시죠.

 

treeMethods.contains = function(target) {
  if (this.value === target) {
    return true;
  } else if (this.children.length !== 0) {
    for (let i = 0; i < this.children.length; i += 1) {
      return this.children[i].contains(target);
    }
  }
  return false;
};

제가 생각했던 로직은 아래 단계와 같습니다. (값을 추가하는 메소드는 생략했습니다)

 

0. children의 배열에 두 개의 객체가 있고, 각각의 value 값이 1, 2 라고 하겠습니다.

1. contains라는 함수 안에서 this는 실행될 때의 객체를 가리키기 때문에, 이것을 재귀로 돌린다면,(this.children[i].contains) 

    if (this.value ~~~) 부터 검사를 시작할 거라 생각했습니다.

2. 맨 처음의 this.value는 값을 할당하지 않았기 때문에, 바로 else if 구문으로 넘어갑니다.

3. children은 배열이기 때문에 for 구문을 사용하여 각각의 객체를 호출합니다.

4. 각각의 객체마다 재귀를 사용하여 모든 값을 검사합니다.

5. for 를 돌았음에도, true가 리턴이 안되면 false가 리턴이 되게 했습니다.

 

하지만, 이 방법에는 return으로 인한 문제점이 있었습니다.

for 구문이 return 으로 인해 0번째 인덱스만 검사하고 종료된다는 것이었습니다.

아....이런......

 

for (let i = 0; i < this.children.length; i += 1) {
  const child = this.children[i];
  if (child.contains(target)) {
    return true;
  }
}

위는 해결했던 코드입니다.

구글링보다는, 뭔가 코드 자체에서 누락된 부분이 있다고 판단하여, 

제 코드만 주구장창 읽고 읽고 또 읽었네요

머릿 속이 그래서 띠잉리ㅣ띠리 하는 거 같습니다.

위의 코드는 for를 끝까지 돌게하는 코드죠. 제가 돌 뻔 했습니다 ^^...

 

요새 재귀를 마스터하고 싶어서 반복문을 재귀로 바꾸려고 하는데, 어렵기만 합니다.

재귀를 좀 사용했다고 느낌이 오면 이렇게 다른 곳에서 팡 터져버리네요...ㅠㅠ

 

이해가 안가면 외우는게 답이랬습니다.

재귀함수도 결국 값을 저장해야 하고, 그 값을 계속 돌리기 위해서는 return이 필요하다는 것!!!

 

재귀에서의 return, 지난 데브로그에서도 return 내용이었는데, base case에 대해서 좀 더 고민을 해 봐야 할 거 같습니다.ㅎㅎ