오늘은 재귀함수에 관해 배우고 있는데 이진 트리 순회를 재귀함수로 할 수 있다는 것을 알게 되었다.
이제 재귀라는 것에 감이 조금 오기 시작했는데 그 감을 일깨워준 문제가 바로 이진 트리 순회 문제였다.
문제는 이진트리를 차례대로 순회하는 것인데 다음과 같이 풀이를 하면 되었다.
재귀함수라고 하는 것은 기본적으로 스택에 누적되어 실행된다.
그리고 그 함수에서 또 함수가 호출되면 현재의 상태를 저장하고 새로운 함수를 실행한다. 새로운 함수가 실행되고 난 뒤 중단되었던 시점으로 돌아와서 다시 마저 작업을 수행하게 된다.
마치, 실생활에서와 같이 비슷한 경우가 아닐까 싶다.
대리점에 가서 휴대폰 개통을 요청 →
대리점에서는 주민등록등본을 요구했는데 없음 →
주민센터에 가서 주민등록등본 발급 요청 →
주민센터 주무관이 주민등록증을 요구함 →
주민등록증을 가지러 집으로 감 →
책상 위에 놓인 주민등록증을 챙김 →
주민센터에 가서 주민등록증을 제출하고 등본을 발급받음 →
대리점으로 돌아와 주민등록등본 제출 →
휴대폰 발급
스택으로 따지면 대리점 위에 주민센터 위에 집에 간 사건이 놓인 것이다. 그리고 차례대로 물건을 챙기면 스택에서 pop되어 해당 프로세스를 마저 실행하는 이치와 비슷하다.
재귀라는 것도 이러한 스택에 하나씩 쌓아가면서 실행한다고 생각하면 된다. 단지, 실생활의 예시와 차이점이 있다면, 재귀는 자기 자신을 호출한다는 것.
이미지 출처: 위키백과
이미 강의에서는 중위순회를 기준으로 수강을 했는데 후위 순회를 직접 작성해 보라는 숙제를 받았다. 연필로 풀고 지우개로 지워가면서 해석하는 것도 중요하겠지만, 기록으로서 남겨두는 것이 좀 더 이롭지 않을까 하는 생각에 이번에도 집필 욕구(?)가 발동하여 이해하기 쉽게 도식화하여 작성해 보게 되었다.
PDF로 보기
웬만하면 배치가 틀어지지 않도록 복붙(Ctrl + C, Ctrl + V) 신공을 사용하였기 때문에 틀린 부분이 있을 수도 있습니다. 발견하시면 피드백 부탁드립니다.
자바스크립트 알고리즘
자바스크립트로 알고리즘을 배우면 언어 자체보다 풀이 과정 자체에 집중할 수 있어서 개인적으로 선호한다.
