하노이 탑은 재귀호출의 대표적인 예다. 또 팩토리얼 연산은 재귀호출의 기본인데, 재귀호출이 무엇인지 알아보고, 점화식과의 관계를 도출하면서 C언어로 어떻게 코딩하는 가를 살펴보는 것이 이번 포스팅의 목표다. 거창한 듯 하지만 재귀호출을 이해만 하면 모든 것이 해결된다. 재귀호출은 간단히 말해서 함수가 자신을 호출하는 경우를 말한다. factorial의 경우를 살펴보자.
factorial은 일련의 수의 곱을 말한다. a!은 1부터 a까지의 곱을 말하는데, for문을 이용해 증가되는 수를 계속 결과값에 곱해서 계산할 수 있다. 그럼 두가지 방법을 살펴보자.
재귀에 대한 생각(factorial)
결과는10! = 3628800으로 같다. 함수의 호출 형태는 같지만 내부적 구조는 다르다. 환경에 따른 성능의 차이도 있다. 재귀호출을 이해한다면 복잡해보이는 문제를 간단하게 풀 수도 있는데, 재귀함수는 스택에 함수와 함수의 인수,지역변수를 재귀호출을 할 경우마다 계속해서 생성하기 때문에, 함수내 인수와, 지역변수가 많을경우 성능이 떨어지고, 스택의 크기를 넘어가도록 재귀를 돌릴 경우 스택오버플로우를 발생시킨다.
또한, 재귀가 회귀하는 시점에 대한 조건이 필요한다. 위 경우는 if(n<=1)이 재귀가 회귀하는 시점이 되고 스택에 쌓인 함수가 다시 해제되는 경계가 된다. n<=1의 조건은 즉 1~10의 곱중에 첫번째 값을 반환 함으로써 각각의 경우를 순서대로 풀어나갈 수 있는 실마리를 제공해준다. 이런 분할적인 재귀의 경우에서 중요한 것은 처음 시작하는 항의 값(반환점의값)이 몇이냐에 따라 결과가 달라지기 때문에, 재귀의 회귀점은 중요한 단서가 되고 꼭 필요한 부분이다. 만약 이 부분이 없다면 무한루프에 빠질 것이다.
팩토리얼의 경우는 너무 간단한 예지만 중요한 예기 때문에, 재귀를 이해하려면 팩토리얼에 대해서 완벽히 이해하는 것이 좋다.
그러면, 좀더 심화하는 차원에서 하노이탑에 대해서 알아보자.
하노이 탑은 세개의 기둥이 있고, 이 기둥에 원판을 끼워넣는 방식은 위에 원판은 무조건 아래의 원판보다 지름이 작아야한다. 즉 크기 순서대로 쌓아져야하고, 이동중에도 이 원칙은 변하지 않는다.
하노이탑의 원리
a에 6개의 원판이 쌓여져 있다. 이 원판을 b로c로 옮기기 위해서는 다음과 같은 작업을 해야한다.
수정 : 중간그림에서 2번과정과 마지막 그림에서 1번 과정을 한번에 이동하는 것으로 수정합니다.
위 작업은 2개의 원판을 c에 옮긴후 3번째원판을 a에서 b로 옮긴뒤 다시 2개의 원판을 c에서 b로 옮겼다. 결과 세개의 원판을 b에 옮겼다. 다음 수행할 작업은 a의 4번째 원판을 c로 옮긴뒤 다시 b의세개의 원판을 c로옮기는 작업을 한 후 a에서 5번째원판을 b로 옮기고 c에서 4개의 원판을 b로 마지막 a의 6번째원판을 c로 옮긴뒤 b의 다섯개의 원판을 C로 옮기는 작업을 한다. 복잡해 보일 수 있지만, 가만히 살펴보면 개수만 틀려질 뿐이지 일반항으로 만들수 있는 작업이 있다.
고등학교 때 배운 점화식을 이용하면 하노이탑을 쉽게 표현할 수 있다. 그럼 이해를 돕기 위해서 점화식을 사용하여 하노이 탑을 표현해보자.
n개를 a에서 c로 옮기는 방법은 n-1개를 옮기는 방법과 구조적으로 동일함을 알 수 있다.
그런데 점화식은 이렇게 일반항을 도출하여서 가지수를 쉽게 구할 수 있지만, 컴퓨터의 경우에는 재귀의 방법을 사용해야한다. 위와같이 구조적으로 동일한 문제를 풀때 사용하는 방법을 분할점령이라고 하는데 원래의 문제가 나눠진 문제와 구조가 같을 때 사용할 수 있다. 하노이탑은 n개를 옮기는 방법은 n-1개를 옮기는 방법과 개수만 다를 뿐 방식은 똑같다. 때문에 n개를 옮기는 하노이탑의 경우 n-1개를 옮기는 경우를 먼저 생각하고 마지막 원판을 옮기는 경우 그리고 또다시 n-1개를 옮기는 경우로 생각하면 된다. n-1개를 옮기는 경우, n-2개를 옮기는 경우 또한 분할된 동일구조의 풀이법으로 해결할 수 있기 때문에, 재귀호출을 사용할 수 있다.
팩토리얼의 경우와는 다르게 n-1개로 나뉘는 경우를 두번 생각하게 한다. a->b로 옮기는 경우와 마지막원판을 옮긴뒤 b에서 c로 옮기는 세번의 작업이 필요하고, 이 세번의 작업을 코드로 나타내야 하는데, 재귀에 익숙지 않다면 생각보다 간단한 문제가 아니다.
때문에 우선 코드를 보면서 설명을 하기로 한다.
하노이의 탑 알고리즘을 짜는 방법은 여러가지가 있겠지만, 가장 간단하다고 생각되는 코드다. 이코드는 위에서 표현한 점화식을 코드로 표현한 것이다. 그리고 14~16줄이 이 알고리즘의 재귀부분다. 원판의 개수를 하나씩 줄여가면서 재귀호출을 하고 있고 위에서 살펴본 봐와 같이 세부분으로 나누어서 순서대로 코드를 짰다. n의 의미는 인수의 경우 전체 원판의 개수를 의미하고 함수내에서는 원판의 번호를 의미하게 된다.
특히 이 알고리즘의 특징은 기둥을 숫자로 표현하는데 있다. 토탈값6과 인수로 전달된 2개의 기둥 그리고 나머지 한개의 기둥으로 나뉘는데, 인수로 전달된 두개의 기둥 외에 기둥은 중간에 원판이 거쳐가는 기둥으로 인수의 전달이 a,b가 되었다면 a->c->b 같이 c 기둥은 중간에 잠시 원판이 거쳐가는 기둥이 된다.
원판을 옮기는 경우는 코드에서 8줄과 15줄이다. 하노이탑의 특징은 1번원판을 한번걸러 한번씩 꼭 움직인다는 것이다. 또한 원판을 몇 번 움직였는가를 알고 싶다면 전역변수를 정해서 8, 15줄에서 ++연산을 하면 된다. (else{}문을 사용하여 if문 첫번째 조건이 회기의 조건으로 만들었다.)
실제로, 하노이의 탑을 보드게임으로 할 경우에는 원판의 개수가 짝수인지 홀수인지에 따라서 첫번째 원판의 이동을 달리 선택해야한다. 하지만 재귀호출의 경우는 역으로 모든경우를 탐색한후 회귀를 하는 방식이기 때문에 짝수인지 홀수인지에 관해서 신경쓸 필요가 없다.