기초가 부족한 탓인지, 요즘 알고리즘, 재귀가 갑자기 더 어렵다고 느껴지기 시작한다.(원래 어려웠지만... 예전에는 당연하게 넘어갔던 것들이 지금 와서 발목을 잡기 시작한다.)
그래서 알고리즘에 자주 나오는 dfs를 구현하면서 재귀에 관련하여 정리를 해보기로 헀다.
우선, Tree구조로 우리가 탐색할 자료를 클래스를 이용하여 만들어 보기로 했다.
Node라는 class를 선언하고, dfsTest라는 인스턴스를 value = 1을주고 만들었다.
위의 상황에서 아래와 같은 코드를 작성하게 되면,
node에 자식붙이기직접 구현해 본 Tree구조
위와 같은 형식의 tree 구조가 만들어지게 된다.
여기까지는 큰 어려움이 없을텐데... 오늘 focus를 두고 싶은 것은, 여기에서 내가 찾고싶은 value를 가지고 있는 해당 객체를 return 하는 함수를 구현 하는 것이다.
우선, 위에서 정의한 dfsTest를 input이라는 배열에 담아 놓았고, 이 배열에서 원하는 value를 dfs형식으로 탐색하는 방식을 구현한 함수는 아래와 같다.
원하는 value를 dfs방식으로 recursion을 이용하여 탐색하는 함수
여기에서 애를 먹었던 부분은, 어이없게도, 43번째 줄에서 return 을 하지 않아서 였다.
처음에 나는 return을 하지 않고, findValue(list, value)를 했을때 어차피 findvalue가 다시 실행되기에, 그리고 어차피 다시 함수가 실행되면 그 안에서 return result가 있기때문에, 따로 return을 해주지 않아도 된다고 생각했다. 하지만 이렇게 되면, 재귀적으로 실행될때 result에 내가 원하는 값이 모두 담김에도 불구하고, undefined가 리턴되게 된다!!! 사실 오늘 내가 가장 강조하고싶은 부분은 여기였다.
왜 재귀적으로 실행 했을때, result가 빈 배열도 아닌, undefined가 리턴되는가?
그 이유는 간단 하였다. 우리가 함수를 실행시켰을때 undefined가 나오는 경우는 return 값이 없을때 이다. 즉, 우리가 처음 실행한 함수를 func1, 그 이후에 재귀적으로 실행되는 함수들을 func2, func3, ... 이라고 했을때, 비록 func2, func3, ...에서 return 값이 있다고 하더라도,애초에 처음 실행된 func1에 return값이 없기 때문에 이러한 undefined사태가 발생하게 되는 것이다.
결론적으로 재귀적으로 함수를 실행하고 싶을때는 꼭 앞에 return 을 붙여주자!(이 간단한것을 난 왜 몰랐을까...)
개인적으로 while문에 매우 익숙하지 않다고 생각이 되기 때문에,
이제 위에 재귀적으로 만들어진 함수를 while문으로 다시 작성해보자.
물론, 위의 경우로 작성한 것은 중복되는 value를 가진 경우가 없다고 가정한 것이고, 멤버쉽체크도 하지 않은 가장 단순한 경우이다. while문을 작성할때에는 내가 돌아볼 list를 컨트롤 하는 것과 조건문을 잘 설정하는데 집중하자
