개발새발 IT

 대학교 1학년 때 하노이 타워를 코딩한 기억이 있는데 다시 해보려니까 잘 되지 않았다. 그래서 코드를 참고하려고 봤는데 참고가 아니라 해석에 매진했다. 멘붕이 오는 줄 알았다.

 재귀적 표현의 시작이자 끝(?)이라 불리는 하노이 타워에 대한 코드는 아래와 같다. 직접 구현해보는게 제일 좋겠지만 어렵다면 코드를 천천히 한 번 해석하는 것도 좋을 것 같다.

main에서 hanoi(3,'A','B','C')의 인자로 함수에 들어가면 hanoi(num-1, first, last, mid)을 만나고 즉, hanoi(3-1,'A','C','B')에 의해서 다시 함수에 들어간다.(first=A mid=C last=B) 이때 다시 hanoi(2-1,'A','B','C')가 호출된다.(first=A mid=B last=C) 그러면 다시 함수로 접근했을 때는 if(num==1)에 걸려서 '원반 1을 A(first)에서 C(last)로 이동'이 된다. 이제서야 hanoi(3-1,'A','C','B')에 대한 처리로 먼저 출력이 이루어진다. (first=A mid=C last=B) 다음으로 hanoi(num-1, mid, first, last)을 만나고 즉, hanoi((3-1)-1, C, A, B)가 되어 if(num==1)에 걸려서 '원반 1을 C(first)에서 B(last)로 이동'이 된다.

드디어 hanoi(3,'A','B','C')의 처리가 되어 출력된다.
그리고 num=3일때 hanoi(num-1, mid, first, last)을 다시 만난다. 즉,  hanoi(3-1, 'B', 'A', 'C')가 호출된다. (first=B mid=A last=C) 그러면 다시 함수로 접근해서 hanoi(num-1, first, last, mid)을  만나고 즉, hanoi((3-1)-1, 'B', 'C', 'A')가 되어 다시 함수에 접근할 때 if(num==1)에 걸려서 '원반 1을 B(first)에서 A(last)로 이동'이 된다. 다음으로 hanoi(3-1, 'B', 'A', 'C')의 처리가 되어 출력된다. (first=B mid=A last=C) 그리고 num=3-1일때 hanoi(num-1, mid, first, last)을 다시 만난다. 즉, hanoi((3-1)-1, 'A', 'B', 'C')가 되어 다시 함수에 접근할 때 if(num==1)에 걸려서 '원반 1을 A(first)에서 C(last)로 이동'이 된다.

 이진 탐색 알고리즘을 재귀적으로 구현해보았다.

while문으로 loop되는 부분을 고려해보면 재귀적 구현의 방법이 나온다.

 팩토리얼을 재귀 함수로 구현하였다.
일단 for문을 이용한 팩토리얼을 간단히 구현해보면 다음과 같다.

 이 경우 i=5이므로 5!에 대한 결과인 120을 출력한다.

이러한 반복적인 과정을 조금 생각해보면 다음과 같이 재귀적으로 구현할 수 있다.