재귀 함수(Recursive Function)

분할 기법

1. K 번째 작은 수 찾기

1) 문제

- 10, 7, 2, 8, 3, 1, 9, 6 이라는 숫자 중에서 세 번째 작은 수는?

 

2) 문제 풀이

- 10, 7, 2, 8, 3, 1, 9, 6 이라는 숫자 중에서 세 번째 작은 수 구하기

1. 10, 7, 2, 8과 3, 1, 9, 6으로 분할

2. 10, 7, 2, 8 중 세 번째 작은 수는 8

3. 3, 1, 9, 6 중 세 번째 작은 수는 6

4. 작은 문제의 해결책이 큰 문제의 해결책으로 이어지지 않는다.

 

2. 분할(Partition)

① 임의로 피벗 설정

② 다운 포인터와 업 포인터 설정

③ 다운은 피벗보다 작거나 같은 것, 업은 피벗보다 크거나 같은 것 찾음

④ 스와핑

⑤ 포인터가 일치하거나 교차할 때까지 ③, ④를 반복

⑥ 업 포인터 위치에 있는 숫자와 피벗을 스와핑

 

1) 분할 방법

 ▪ 피벗보다 작은 것은 왼쪽으로, 피벗보다 큰 것은 오른쪽으로

 ▪ 전체 데이터가 정렬된 상태는 아님

 ▪ 모든 데이터가 정렬되어도 피벗 위치는 불변

 ▪ K가 4라면 네 번째 작은 수를 이미 찾은 것임

 

2) 세 번째 작은 수 찾기

▪ 분할된 왼쪽에 대해서 다시 파티션을 가함

▪ 분할된 오른쪽에 대해서 다시 파티션을 가함: Self-swap

 

재귀 함수의 작성 및 효율성

1. 재귀 함수의 작성

1) 방법

Step 1

 ▪ 더 작은 문제로 표시할 수 있는지 시도

  - 문제 크기를 하나씩 줄이는 방법

  - 반으로 줄이는 방법

  - 다른 여러 개의 작은 문제의 조합으로 표시하는 방법

 ▪ 문제 크기 파라미터 n을 확인

Step 2

 ▪ 문제를 직접 풀 수 있는 것이 어떤 경우인지 베이스 케이스 확인

Step 3

 ▪ n이 줄어서 반드시 베이스 케이스를 만나는지 확인

 ▪ n이 양수인지 음수인지, 짝수인지 홀수인지, 또는 부동소수인지 정수인지 모든 경우에 대해 모두 검증

Step 4

 ▪ 베이스 케이스와 베이스 케이스가 아닌 경우를 나누어서 코드를 작성

 

2) 순환 알고리즘

 ▪ 순환 알고리즘은 다음과 같은 부분들을 포함함

 - 순환 호출을 하는 부분

 - 순환 호출을 멈추는 부분

 

3) 만약 순환 호출을 멈추는 부분이 없다면?

- 스텍 메모리를 꽉 채울 때까지 사용하다가 시스템 오류가 발생할 때까지 호출하게 됨

2. 재귀 호출의 효율성

1) 순환과 반복

 ▪ 컴퓨터에서의 되풀이

2) 활성화 레코드의 비효율

 ▪ 공간적 비효율(저장 공간)

 ▪ 시간적 비효율(저장, 복원에 걸리는 시간)

 - 가능하다면 반복문으로 대치하는 것이 유리!

 

3. 재귀 호출의 반복문 전환

int Factorial(int n)
{ 
	int product = 1;
	for (int i = 1; i <= n; i++)
		product *= i;
	return product;
}

void Reverse(char S[ ], int Size)
{ 
	while (Size > 0) 
	{ 
    	printf("%c", S[Size-1]); 
		--Size;
	} 
} 

int Fibonacci(int n)
{ 
	int A[Max];
	F[0] = 1; F[1] = 1;
	for (int i = 2; i <= n; i++) 
		F[i] = F[i-2] + F[i-1];
	return (F[i]);
}

- 팩토리얼의 반복적 구현

int factorial_iter(int n)
{
	int k, v=1;
	for(k=n; k>0; k--)
		v = v*k;
	return(v);
}

1. 하노이의 탑 문제 

- 문제는 막대 A에 쌓여있는 원판 n개를 막대 C로 옮기는 것이다!(단, 다음의 조건을 지켜야 함)

 ▪ 한 번에 하나의 원판만 이동할 수 있다.

 ▪ 맨 위에 있는 원판만 이동할 수 있다.

 ▪ 크기가 작은 원판 위에 큰 원판이 쌓일 수 없다.

 ▪ 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 한다.

 

2. n = 3인 경우

3. 일반적인 경우

재귀 함수를 이용한 복잡한 문제의 해결

// 막대 from에 쌓여있는 n개의 원판을 막대 tmp를 사용하여 막대 to로 옮긴다.

void hanoi_tower(int n, char from, char tmp, char to) 
{ 
	if (n==1){ 
		from에서 to로 원판을 옮긴다. 
	} 
	else
	{ 
		hanoi_tower(n-1, from, to, tmp); 
		from에 있는 한 개의 원판을 to로 옮긴다. 
		hanoi_tower(n-1, tmp, from, to); 
	} 
}

n-1개의 원판을 A에서 B로 옮기고 n번째 원판을 A에서 C로 옮긴 다음, n-1개의 원판을 B에서 C로 옮기면 된다.

#include <stdio.h>
void hanoi_tower(int n, char from, char tmp, char to)
{
	if( n==1 ) printf("원판 1을 %c 에서 %c으로 옮긴다.\n",from,to);
	else 
    {
		hanoi_tower(n-1, from, to, tmp);
		printf("원판 %d을 %c에서 %c으로 옮긴다.\n",n, from, to);
		hanoi_tower(n-1, tmp, from, to);
	}
}

main()
{
	hanoi_tower(4, 'A', 'B', 'C');
}