재귀는 수학적으로 자신의 정의에 자기 자신이 포함되는 경우를 말합니다. 컴퓨터 언어에서 재귀호출은 비슷하게 어떤 함수의 정의가 자기 자신을 호출하는 경우를 의미하며, 수학의 재귀는 컴퓨터 언어의 재귀호출로 표현될 수 있습니다.흔히 수학의 재귀적 표현은 쉽게 이해하지만 재귀호출과 컴퓨터가 내부적으로 그것을 어떻게 해석하고 실행하는지는 이해하는데 어려움을 겪는 분들이 많습니다. 재귀호출을 이해하기 위해서는 스택과 함수에 대한 근본적인 이해가 있어야 합니다. 이번 장에서는 이런 측면에서 재귀호출을 이해하고 해석하는 방법에 대해서 알아보고자 합니다.
저 역시 그렇지만 재귀호출로 멋지게 구현한 알고리즘을 보면 어떤 아름다운 예술을 보는듯한 느낌이 든다는 분들이 많습니다. 그만큼 간결하면서도 미적으로 완성된 코드를 만들 수 있음을 의미합니다. 연습을 통해 재귀호출에 대해 완벽하게 이해한다면 복잡한 문제를 해결할 수 있는 또 하나의 강력한 무기를 가지게 되는 겁니다.
실제로 어떤 방법으로도 효율적인 해답이 찾아지지 않는 문제에 대한 유일한 해법이 전수 탐색(Exhaustive Search)일 경우가 많으며, 이 전수 탐색은 재귀호출로 구현되는 경우가 많습니다.
이제 본격적으로 재귀호출의 아름다움에 빠져들어 보도록 합시다.
강의 자료
강의 동영상
8.0 재귀호출 - 시작 : 재귀호출은 코드를 아름답고 간결하게 만들어 줍니다. 처음에는 약간의 어려움이 있겠지만 재귀호출을 배우고 나면 문제 해결에 큰 무기를 하나 획득하는 겁니다.
8.1 재귀호출의 개념 : 재귀호출은 자기 자신을 호출하는 함수를 뜻합니다. 하지만 몇가지 추가 조건을 충족해야 합니다. 예제를 통해서 재귀호출의 정의에 대해 알아 봅니다.
8.2 피보나치 수열 : 재귀적으로 정의되는 피보나치 수열에 대해 알아보고, 이를 구현해 봅니다. 머릿속으로 어떻게 돌아가는지 이해해야 합니다.
8.3 하노이의 탑 : 전통적인 퍼즐인 하노이의 탑 문제를 이해하고 해결하는 방법을 알아봅니다. 재귀호출을 이용하면 하노이의 탑 문제를 극적으로 풀 수 있습니다.
8.4 플러드필 (칠하기) : 기하학적으로 경계 내의 어떤 영역을 특정한 색으로 칠하는 문제를 플러드필(Flood Fill)이라고 합니다. 재귀적인 해법이 없다면 매우 해결하기 어려운 문제입니다. 플러드필 알고리즘을 구현하고 실행해 봅니다.
8.5 프랙탈 트리 : 프랙탈 이론은 단순한 도형이 자기 복제를 통해 복잡한 도형으로 발현되는 것을 다룹니다. 매우 흥미롭고 신기한 결과들을 볼 수 있습니다. 프랙탈 이론을 이용하여 자연스러운 나무 모양을 그리는 방법을 알아봅니다.
8.6 파일 찾기 (RFF) : 자주 사용하는 파일 찾기 프로그램을 어떻게 구현할 수 있을지 생각해 보셨나요? 디렉토리와 파일 구조는 트리 구조이기 때문에 트리의 순회를 재귀적으로 구현하면 파일 찾기 기능을 구현할 수 있습니다.
8.9 재귀호출 - 결론 : 이 장에서는 재귀호출의 개념을 배웠고, 재미있는 예제를 통해서 재귀호출의 묘미를 살펴 보았습니다. 정리합니다.
관련글 |
- C++로 배우는 알고리즘
- 7장 : 트리
- 9장 : 정렬의 기본
댓글 없음:
댓글 쓰기