[자료구조] : 재귀함수2(C)

이번 시간에는 재귀함수 두 번째 시간이다. 재귀함수를 이용하면 복잡한 코드를 간결하게 표현 가능하다. 대표적인 예시로 하노이탑이 있다.

하노이 탑은

작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제다. 이 상태에서 모든 원반을 세 번 째 기둥으로 최소한 횟수로 옮기면 된다. 원반은 1개씩만 옮길 수 있고, 큰 원반을 작은 원반 위에 쌓을 수 없다.

• 첫 번째 기둥 : 시작 기둥
• 목적지의 기둥 : 목표 기둥 (세 번째)
• 남은 중간의 기둥 : 중간 기둥 (두 번째)

<원반 3개를 옮기는 과정>

<원반 2개를 옮기는 과정>

이와 같은 흐름을 구현한 프로그램이다.

<코드>

#include <stdio.h>
// 원반 [1] ~ 원반[no]를 x 기둥에서 y기둥으로 옮김 
void move(int no, int x, int y)
{
	if (no > 1)
	{
		move(no - 1, x, 6 - x - y); // 그룹을 시작 기둥에서 중간 기둥으로 
	}printf("원반[%d]를(을) %d기둥에서 %d기둥으로 옮김\n", no, x,y);
	if (no > 1)
		move(no - 1, 6 - x - y, y); //그룹을 중간 기둥에서 목표기둥으로 
}



int main()
{
	int n;
	printf("하노이의 탑\n 원반 개수 : ");
	scanf_s("%d", &n);
	move(n, 1, 3);
	return 0;

}

• 왜 6-x-y로 표기했는가? -> 기둥 번호가 1,2,3일 때, 기둥 번호의 합이 6이다.
  시작 기둥, 목표 기둥이 어느 기둥이더라도 중간 기둥은 6-x-y다.
• move 함수는 다음과 같이 진행된다.

1. 바닥 원반을 제외한 그룹(원반[1] ~ 원반[no-1])을 시작 기둥에서 중간 기둥으로 옮긴다.
2. 바닥 원반 no를 시작 기둥에서 목표 기둥으로 옮겼음을 출력
3. 바닥 원반을 제외한 그룹(원반[1] ~ 원반[no-1])을 중간 기둥에서 목표 기둥으로 옮긴다.

<결과>