[자료구조] [7] 순환

순환, 또는 재귀 호출이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법.

트리 구조에서 많이 사용된다.

 

순환 호출의 내부적인 구현

-시스템 스택과 활성 레코드

A라는 함수에서 함수 B가 호출되면, (B가 자기자신, 즉 A라도 전혀 문제가 없다)

1. B가 끝나고 A의 처리 상황을 복원할 수 있도록 A의 복귀 주소, 사용하던 지역 변수 등의 자료를 모아 활성 레코드를 준비. 이를 시스템 스택에 저장.
2. B의 코드 시작 위치로 이동하여 처리를 시작(B가 자기자신, 즉 A라면 A의 시작위치로 이동)
3. 호출된 함수 B가 끝나면 스택에서 복귀주소를 꺼내 자신을 호출한 함수 A로 되돌아간다.

순환호출이 중첩될수록 스택에 활성 레코드들이 쌓인다.

함수호출마다 새로운 지역변수를 만들 수 있기에 이전 호출과 구분이 가능해 순환 호출이 가능한 것.

 

int factorial(int n) {
	if(n == 1) return 1;
	else factorial(n-1);
 }
 void main() {
 	factorial(3);
 }

위 재귀 함수를 호출했을 때 시스템 스택의 변화 과정은 (적힌 순서대로 스택에 들어간 상태)
factorial(3) -> factorial(3)-factorial(2) -> factorial(3)-factorial(2)-factorial(1) -> factorial(3)-factorial(2) -> factorial(3)

 

트리 알고리즘의 순회, 노드의 삽입연산 등 순환이 많이 사용되는데 이 때 순환으로 구현하면 반복에 비해 코드가 간단.

그러나 실행속도 면에서는 함수 호출의 부담때문에 반복보다 느리다. (순환이 더 빠른 예제도 존재한다.)

 

 

분할정복(divide and conquer)

팩토리얼의 순환호출 함수를 보면 전체 문제의 일부만을 먼저 해결한 다음, 순환 호출을 한다.

int factorial(int n) {
if(n == 1) return 1;
else return ( n * factorial(n-1) );
}
// 해결된 부분 / 남아있는 부분

일부가 해결되면 남은 문제는 원래 문제보다 쉬워지고, 더 쉬워진 문제도 동일한 방법으로 처리.

순환호출이 일어날 때 마다 문제의 크기가 반드시 작아져야 한다.

이런식으로 어떤 문제를 더 작은 동일한 문제들로 분해하여 해결하는 방법을 분할정복이라 한다.

 

팩토리얼 함수 계산, 피보나치수열, 이항계수 계산, 각종 이진트리 알고리즘, 이진 탐색, 하노이 탑 등은 문제가 순환적으로 정의되어 있어 순환 알고리즘을 사용하는 것이 자연스럽다.

 

-피보나치 수열

보통 순환을 사용하면 코드가 단순화,가독성이 높아지지만 같은 계산을 몇 번씩 반복해야 된다면 문제.

대표적인 예가 피보나치 수열.

 

fib(n) = { 0        n=0

           { 1        n=1

           { fib(n-2)+fib(n-1)   otherwise

 

일반적 경우, 앞의 두개 숫자를 더해서 뒤의 숫자를 만들면 된다.

피보나치 수열은 정의 자체가 순환적이라 순환 호출을 사용하여 구현하는 것이 자연스럽지만,

순환 호출을 사용해 구현하면 매우 비효율적이다.

// 순환적인 피보나치수열 계산 함수
int fid(int n)
{
	if(n==0) return 0;
    if(n==1) return 1;
    return (fib(n-1) + fib(n-2))
}

해당 함수는 fib(6)을 구하려면 fib()함수가 총 25번 순환 호출 된다. 

이유는 중간에 계산되었던 값을 기억하지 않고 다시 계산하기 때문이다. 

예를 들어 n이 30이면 약 300만번의 함수 호출이 필요하다.

n이 커지게 되면 엄청난 순환호출이 필요하게 되어 순환호출을 사용해 피보나치수열을 계산하는 것이 거의 불가능해진다.

 

따라서 반복구조를 이용하여 구현하는 것이 훨씬 효율적이다.

// 반복적인 피보나치 수열 계산 함수
int fib_iter(int n) {
	int i, tmp, current, last;
    if( n<2 ) return n;
    else {
    	last = 0;
        current = 1;
        for (i=2;i<=n;++i) {
        	tmp = current;
            current += last;
            last = tmp;
        }
        return current;
    }
 }

 

 

- 순환 응용 : 하노이탑

한 막대에 크기대로 쌓아놓은 원판을 3개의 막대 중 다른 한 곳으로 모두 옮겨 놓도록 하는 문제.

• 한 번에 하나의 원판만 이동
• 맨 위에 있는 원판만 이동 가능
• 크기가 작은 원판위에 큰 원판이 쌓일 수 없다.(n개의 원판의 크기는 모두 다르다)
• 원판의 이동 횟수는 최소로 한다.
• 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 한다.

// n개의 원판을 가지는 하노이의 탑 문제의 해답
// 막대 from에 쌓여있는 n개의 원판을 막대 temp를 사용하여 막대 to로 옮긴다.

void hanoi_tower(int n, char from, char temp, char to) {
	if(n==1) {
    	//from에서 to로 원판을 옮긴다.
        printf("원판 1을 %c에서 %c로 옮긴다.\n",from,to);
    }
    else {
    	//1. from의 맨 밑 원판을 제외한 나머지 원판들을 temp로 옮긴다.
        hanoi_tower(n-1,from,to,temp);
        //2. from에 있는 한 개의 원판을 to로 옮긴다.
        printf("원판 %d을 %c에서 %c로 옮긴다.\n",n,from,to);
        //3. temp의 원판들을 to로 옮긴다.
        hanoi_tower(n-1,temp,from,to);
    }
 }
 void main() {
 	hanoi_tower(4,'A','B','C');
 }

n-1개의 원판을 이동하는 1과 3은 막대의 위치만 달라졌을 뿐 원래 문제의 축소된 형태.

1은 to를 사용하여 from->temp 로 n-1개의 원판을 이동하는 문제.

3은 from을 사용하여 tmep->to로 n-1개 원판을 이동하는 문제.

 

- 순환 응용: 미로 탐색

덱을 스택처럼 사용하면 깊이 우선 탐색(DFS), 큐처럼 사용하면 너비 우선 탐색(BFS)이 가능.

순환호출 이용하면 자료구조 사용하지 않고도 미로 탐색이 가능.

이 프로그램은 스택을 사용하지 않았지만 실제로는 스택을 사용한 것과 동일.

함수 호출 과정에서 자동으로 시스템 스택이 사용되기 때문이다. 따라서 순환호출을 이용하면 깊이우선 탐색(DFS)을 할 수 있게 된다.

순환 호출로 큐를 사용하는 너비우선 탐색은 불가능하다.

#include <stdio.h>

#define MAZE_SIZE 6


typedef struct Position {
	int x;
	int y;
}POS;

int maze[MAZE_SIZE][MAZE_SIZE] = { // 0=길,1=벽,2=입구,3=출구.4=이미 가본 곳
	{1,1,1,1,1,1},
	{2,0,1,1,1,1},
	{1,0,0,0,1,1},
	{1,0,1,0,1,1},
	{1,0,1,0,0,3},
	{1,1,1,1,1,1}
};

POS enter = { 0,1 };
POS exit = { 5,4 };
bool b_isDone = false;

bool is_valid(int x, int y) {
	if (x < 0 || y < 0 || x >= MAZE_SIZE || y >= MAZE_SIZE) 
		return false;
	else return maze[y][x] == 0 || maze[y][x] == 3;// 갈수 있는 곳은 0과 출구
}

void search_recursion(int x,int y) {
	if (b_isDone)
		return;
	printf(" (%d,%d) ", x, y); // 현재 위치 출력
	if (x == exit.x && y == exit.y) {
		b_isDone = true;
		return;
	}
	maze[y][x] = 4; // 4=이미 가본곳 표시
	// 현재 위치의 상,하,좌,우 위치 검사
	if (is_valid(x - 1, y))
		search_recursion(x - 1, y);
	if (is_valid(x + 1, y))
		search_recursion(x + 1, y);
	if (is_valid(x, y - 1))
		search_recursion(x, y - 1);
	if (is_valid(x, y + 1))
		search_recursion(x, y + 1);

}

void main() {
	search_recursion(0, 1);
	if (b_isDone)
		printf("\n => 출구가 탐지되었습니다.\n");
	else
		printf("\n => 출구를 찾지 못했습니다.\n");

}