재귀 알고리즘 _ 하노이 타워 문제

'윤성우의 열혈 자료구조'의 Ch.2 재귀(Recursion)를 보면서 요약한 내용입니다.

---

재귀 알고리즘에서는 다음 두 가지를 잘 생각해야 한다.

1. 재귀의 탈출 조건

2. 반복되는 패턴

---

[EX 1] 팩토리얼 구하기

팩토리얼의 종료조건과 반복패턴

👇 소스코드

#include <stdio.h>

int recursive_factorial(int nb)
{
    if (nb <= 0)
        return (1);
    return (nb * recursive_factorial(nb - 1));
}

int main(void)
{
    int nb;

    nb = 6;
    printf("%d! = %d\n", nb, recursive_factorial(nb));
}

 

[EX 2] 피보나치 수열 구하기

피보나치 수열의 종료조건과 반복 패턴

👇 소스코드

#include <stdio.h>

int fibonacci(int index)
{
    if (index == 1)
        return (0);
    else if (index == 2)
        return (1);
    else
        return (fibonacci(n-1) + fibonacci(n-2));
}

int main(void)
{
    int i;
    for(i = 1; i < 15; i++)
        printf("%d ", fibonacci(i));
    return (0);
}

 

[EX 3] 하노이 타워

하노이 타워는 재귀의 반복 패턴을 찾는 것이 간단하지 않다. 

출처 : https://www.geeksforgeeks.org/c-program-for-tower-of-hanoi/

원반이 3개인 하노이타워 문제는 위와 같이 7개의 단계를 거쳐 풀 수 있다. 

 

그림을 보면서 패턴을 찾아보자. 

 

원반 1, 2, 3을 C로 옮기는 문제를 해결하려면,

원반 1, 2를 B로 먼저 옮겨야함을 알 수 있다.

그다음, 3을 C로 옮기고,

1, 2를 다시 C로 옮겨야 한다.

 

마찬가지로 원반이 4개라면, 원반 1,2,3 을 먼저 B로 옮기고 4를 C로 옮긴 뒤, 1,2,3 을 C로 옮겨야 한다.

 

🚩 패턴을 일반화하면

n 개의 원반을 A에서 C로 옮길 때,

1. 원반 n - 1 개를 A에서 B로 이동
2. 큰 원반을 A에서 C로 이동
3. 원반 n - 1 개를 B에서 C로 이동

🚩 종료조건은 옮길 원반이 1개일 때이다.

 

소스코드

#include <stdio.h>

void HanoiTower(int num, char from, char by, char to)
{
	if (num == 1)
	{
		printf("원반 1을 %c에서 %c로 이동\n", from, to);	
	}
	else
	{
		// Move n - 1 number of disks from A to B
		HanoiTower(num - 1, from, to, by);
		// Move the disk n from A to C
		printf("원반 %d를 %c에서 %c로 이동\n", num, from, to);
		// Move n - 1 number of disks from B to C
		HanoiTower(num - 1, by, from, to);
	}
}

int main()
{
	// Move 3 number of disks from A to C
	HanoiTower(3, 'A', 'B', 'C');
	return (0);
}

 

실행결과