재귀함수 - 2장

재귀함수.

재귀함수는 나(함수)자신을 재 호출하는 함수를 이야기한다.

void Recursive()
{
    pritnf("Recursive Call");
    Recursive(); 
}

(위의 경우는 탈출조건이 없는 재귀함수)

 

재귀함수는 함수의 호출순서를 스택으로 쌓고 탈출조건이 완료되면 마지막에 호출되었던 녀석이 역순으로 종료되는 구조.

 

https://deftkang.tistory.com/36

이 재귀함수는 탈출조건이 존재한다. 매개변수에 인자로 넘겨온 수가 0보다 작게되면 종료.

그림을 보면 호출의 순서와 반환의 순서는 역순이다.

 

재귀함수를 쓸 수 있는 간단한 예제를 본다.

#include <cstdio>

int Factorial(int num)
{
    if(num == 1)
        return 1;
    else
        return num * Factorial(num - 1);
}
int main()
{
	printf("5!의 값은 : %d",Factorial(5));
	return 0;
}

   

Factorial함수의 매개변수에 인자로 5를 넘기게 되면

1. else문 - return 5 * Factorial(4) -> 2번 호출

2. else문 - return 4 * Factorial(3) -> 3번 호출

3. else문 - return 3 * Factorial(2) -> 4번 호출

4. else문 - return 2 * Factorial(1) -> 5번 호출

5. if문 - return 1.

-> 재귀의 종료. 이제 호출된 순서를 역순으로 올라간다.

4. else문 - return 2 * 1 (2 리턴)

3. else문 - return 3 * 2 (6 리턴)

2. else문 - return 4 * 6 (24 리턴)

1. else문 - return 5 * 24 (120 리턴)

종료.

 

하노이 타워

하노이 타워는 하나의 막대에 쌓여 있는 원반을 다른 하나의 원반에 그대로 옮기는 방법에 관한것.

출처 윤성우 자료구조 동영상강좌

(자료구조와는 관련없지만 재귀를 통해 간단하게 해결할 수 있는문제)

 

저 위의 규칙을 지키면서 A 원반3개를 C로 옮기는 방법은 이렇다.

1. 제일 작은 원반을 C로 이동

2. 두번쨰로 큰 원반을 B로 이동

3. 제일 작은 원반을 B로 이동

4. 제일 큰 원반을 C로 이동

5. 제일 작은 원반을 A로 이동

6. 두번째로 큰 원반을 C로 이동

7. 제일 작은 원반을 C로 이동.

 

이러한 일련의 과정이 반복구조가 존재한다.

작은 구조로 나눠본다면, 큰 원반을 C에 옮기기 위해 나머지 작은 원반이 B로 이동한다는 점이다.

 

즉 제일 큰 원반을 제외한 나머지 작은 원반 n - 1개를 A에서 B로 이동.

큰 원반을 A에서 C로 이동.

나머지 원반을 B에서 C로 이동이다.

 

대부분의 코드에서는 이 '경유지'변수 때문에 헷갈리는 경우가 많은데, 결국 문제를 모두 세분화했을때.

3이 들어오면 3,2,1 원반이 하나라면 바로 C로이동. 돌아와서 2개라면 B로 이동. 3개라면 C로이동.

쓰면서도 말이 어려운데. 코드를 본다.

 

#include <cstdio>

void move(int num,char from, char to)
{
	printf("원반 %d을(를) %c에서 %c로 이동\n", num, from, to);
}

void HanoiTowerMove(int num, char a, char b, char c)
{
	if (num == 1)
	{
		move(num,a, c); // 제일 큰 원반(세분화)은 c로 이동
	}
	else
	{
		HanoiTowerMove(num - 1, a, c, b); // n - 1개의 원반을 A에서 B로 이동
		move(num, a, c);
		HanoiTowerMove(num - 1, b, a, c); // n - 1개의 원반을 B에서 C로 이동
	}
}
int main()
{
	HanoiTowerMove(3, 'A', 'B', 'C');
	return 0;
}

처음 메인함수에서 3개의 원반과 A,B,C. (A<B<C순으로 크다)

 

 

위는 윤성우님의 열혈 자료구조를 참고하여 복습한것을 정리한 내용입니다.