자료구조 - 재귀의 활용

1. 피보나치 수열로 재귀함수 알아보기

 

 

피보나치 수열 : 재귀적인 형태를 띠는 대표적인 수열

 

코드

#include <stdio.h>
int fibo(int n)
{
	if (n == 1)
		return 0;
	else if (n == 2)
		return 1;
	return fibo(n - 1) + fibo(n - 2);
}

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

 

결과

0 1 1 2 3 5 8 13 21 34 55

 

 

---

2. 재귀 함수의 실행 흐름 알아보기

다음과 같이 fibo(7)을 호출했을 때

다음과 같이 많은 수의 함수 호출을 동반한다.

 

 

return fibo(n-1) + fibo(n-2)

 

다음과 같은 식이 있을 때 + 연산자 왼쪽에 있는 fibo 함수호출이 완료되어야 비로소 + 오른쪽에 있는 fibo 함수호출이 실행된다.

 

 

 

즉 다음과 같이 왼쪽 함수가 다 실행되고 나서야 오른쪽 함수가 실행되는 것을 알 수 있다.

 

---

3. 하노이타워

하노이 타워 문제는 A에 있는 원반들을 모두 C로 옮기는데 이 때 원반은 하나씩만 옮길 수 있으며 옮기는 과정에서 작은 원반 위에 큰 원반이 올려져서는 안된다.

 

먼저 원반 3개로 가정했을 때 맨 위에 있는 원반을 A에서 C로 옮기고 가운데 원반은 A에서 B로 옮긴 후

 

그 다음 C에 있던 원반을 B로 옮긴다.

 

큰 원반을 A에서 C로 옮긴다.

 

B에 있던 가장 작은 원반을 A로 옮긴다.

 

마지막으로 B에 있던 중간 크기의 원반을 C로 옮긴 후 A에 있던 원반을 C로 옮긴다.

 

 

이 부분을 크게 보자면 (세세한 부분 제외하고)

 

1. 작은 원반 2개(맨 아래 원반 제외)를 A에서 B로 이동
2. 큰 원반 1개를 A에서 C로 이동
3. 작은 원반 2개를 B에서 A로 이동

 

 

그러면 다음과 같은 재귀적 식을 표현할 수 있다.

 

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

 

 

다음은 원반의 갯수가 1,2,3 개 있을 때 옮기는 방법을 나타낸 것이다.

 

여기서 원반이 3개일 때 크게 보면

 

위에서 2개의 원반을 B로 옮기는 상황(A->B),

맨 아래 원반을 C로 옮기는 상황(A->C),

그리고 나머지 원반 2개를 C로 옮기는 상황(B->C)

 

총 3개로 볼 수 있으며 A->C 를 제외한 두 개의 상황은 각각 3개의 상황으로 나눌 수 있다.

이를 코드로 표현하면 다음과 같다.

 

 

코드

 

실행결과