재귀 알고리즘 분석(Recursive Algorithm)

재귀 알고리즘 분석

재귀 알고리즘 분석에는 두가지 분석 방법이 있습니다.

• 하향식(top down)
• 상향식(bottom up)

아래의 예제를 하여금 분석해봅시다

#include <stdio.h > 

/*--- 재귀 함수 recur( ) ---*/
void recur(int n)
{
	if (n > 0) {
		recur(n - 1);
		printf("%d\n", n);
		recur(n - 2);
	}
}

int main(void)
{
	int x;
	printf("정수를 입력하세요 : ");
	scanf("%d", &x);

	recur(x);

	return 0;
}

이 예제의 재귀 호출은 함수 안에서 2번 실행됩니다. 그러면 실제 동작은 매우 복잡해집니다. 이런 복잡한 구조의 재귀 함수는 좀 더 전략적으로 분석해야 합니다. recur함수를 하향식과 상향식 두가지 방법으로 분석합니다. 입력값이 4이면 출력 결과 값은 1 2 3 1 4 1 2 입니다.

햐향식 분석

• 첫번째 함수 실행
  1번 recur(3)를 실행
  2번 4 출력
  3번 recur(2)를 실행

중요한점은 위의 1번 실행이 완료가 되어야 2, 3번도 실행이 됩니다. 따라서 recur(3)을 실행합니다.
전달 받은 값(n)이 0이하면 recur 함수는 아무 일도 하지 않으므로 검은색 빈 상자입니다.

recur(3)부터 시작하여야 함으로 왼쪽 화살표를 따라서 이동합니다. 그리고 빈 상자를 만나면 다시 원래 상자로 돌아오면서 가운데 출력하고 이어서 오른쪽 화살표를 따라 한칸 아래 상자로 이동합니다. 이렇게 하나의 작업이 완료되어야 한 칸 위의 상자로 돌아갈 수 있습니다.

이처럼 가장 위쪽에 위치한 함수 호출부터 시작해 계단식으로 자세히 조사해 가는 분석 기법을 하향식 분석(top-down analysis)이라고 합니다. 이 안에는 recur(1), recur(2)의 호출이 여러 번 있습니다. 꼭대기(top)부터 아래로 분석하면 이렇게 같은 함수의 호출이 여러 번 나올 수 있기 때문에 '햐향식 분석이 반드시 효율적이다'라고는 말할 수는 없습니다.

상향식 분석

하향식 분석과는 반대로 아래쪽부터 쌓아 올리며 분석하는 방법이 상향식 분석(bottom-up analysis)입니다. recur 함수는 n이 양수일 때만 실행하므로 먼저 recur(1)을 생각합니다.

• recur(1)이 수행하는 작업은 다음과 같습니다.
  1번 recur(0)을 실행
  2번 1을 출력
  3번 recur(-1)을 실행

여기서 1, 3번은 출력할 내용이 없습니다. 따라서 2번의 1만 출력합니다.

• 다음 recur(2)에 대해 생각해 봅시다.
  1번 recur(1)을 실행
  2번 2를 출력
  3번 recur(0)을 실행

1번은 1을 출력하고 2번은 2을 출력하고 3번은 출력할 내용이 없습니다.

• 전체 과정을 보자면 다음과 같습니다.
  

재귀 알고리즘의 비재귀적 표현

recur 함수를 재귀 호출을 사용하지 않고 구현하는 방법에 대해 살펴보겠습니다.

• 꼬리 재귀의 제거(tail recursion)
  함수의 꼬리에서 재귀 호출하는 함수 recur(n - 2)라는 말은 '인자로 n - 2를 전달하여 recur 함수를 호출한다'는 의미입니다. 따라서 이 호출은 아래처럼 바꿀 수 있습니다. n의 값을 n - 2로 업데이트하고 함수의 시작 지점으로 돌아갑니다.

#include <stdio.h> 

/*--- 함수 recur (맨끝 재귀를 삭제) ---*/
void recur(int n)
{
Top:
	if (n > 0) {
		recur(n - 1);
		printf("%d\n", n);
		n = n - 2;
		goto Top;
	}
}

int main(void)
{
	int x;

	printf("정수를 입력하세요. :");
	scanf("%d", &x);

	recur(x);

	return 0;
}

그림으로 보자면 아래와 같습니다.

이렇게 하면 꼬리 재귀를 제거할 수 있습니다.

• 재귀의 제거
  꼬리 재귀와는 다르게 앞에서 호출한 재귀 함수의 제거는 쉽지 않습니다. 변수 n의 값을 출력하기 전에 recur(n - 1)을 먼저 수행해야 하기 때문입니다. 예를 들어, n = n - 1로 구현하면 n은 3이 되기 때문에, 재귀 호출 recur(3)의 처리가 완료되지 않으면 n의 값인 '4'를 저장해야 합니다. 따라서 변수 n의 값을 잠시 저장해야 합니다. 이런 데이터 구조가 stack입니다. 다음은 스택을 이용하여 비재귀적으로 구현한 recur 함수입니다.

#include <stdio.h> 
#include <stdlib.h>

typedef struct {
	int max;		/* 스택 용량 */
	int ptr;		/* 스택 포인터 */
	int* stk;		/* 스택의 첫 요소에 대한 포인터 */
} IntStack;
/*--- 스택 초기화 ---*/
int Initialize(IntStack* s, int max)
{
	s->ptr = 0;
	if ((s->stk = calloc(max, sizeof(int))) == NULL) {
		s->max = 0;								/* 배열의 생성에 실패 */
		return -1;
	}
	s->max = max;
	return 0;
}
/*--- 스택에 데이터를 푸시---*/
int Push(IntStack* s, int x)
{
	if (s->ptr >= s->max)		/* 스택이 가득 참 */
		return -1;
	s->stk[s->ptr++] = x;
	return 0;
}
/*--- 스택에서 데이터를 팝 ---*/
int Pop(IntStack* s, int* x)
{
	if (s->ptr <= 0)		/* 스택이 비어 있음 */
		return -1;
	*x = s->stk[--s->ptr];
	return 0;
}
/*--- 스택 종료 ---*/
void Terminate(IntStack* s)
{
	if (s->stk != NULL)
		free(s->stk);		/* 배열을 삭제 */
	s->max = s->ptr = 0;
}
/*--- 스택이 비어 있는가? ---*/
int IsEmpty(const IntStack* s)
{
	return s->ptr <= 0;
}

/*--- 함수 recur (재귀를 삭제) ---*/
void recur(int n)
{
	IntStack stk; 		/* 스택 */
	Initialize(&stk, 100);
Top:
	if (n > 0) {
		Push(&stk, n); 	/* n 값을 푸시 */
		n = n - 1;
		goto Top;
	}
	if (!IsEmpty(&stk)) {	/* 스택이 비어 있지 않으면 */
		Pop(&stk, &n);  /* 값을 저장한 n을 팝 */
		printf("%d\n", n);
		n = n - 2;
		goto Top;
	}
	Terminate(&stk);
}

int main(void)
{
	int x;

	printf("정수를 입력하세요. :");
	scanf("%d", &x);

	recur(x);

	return 0;
}

위의 그림과 아래를 참고하여 과정을 살펴보면

1. n값을 푸시하여 왼쪽 화살표를 따라갑니다(n = n - 1)
2. 돌아오면 pop한 스택의 값을 출력합니다.
3. 오른쪽 화살표를 따라 값니다(n = n - 2)

recur 함수의 코드를 자세히 살펴봅시다.

1. 그림 A ~ D : n > 0일때 push작업과 n = n - 1을 하여 goto문이 실행되어 레이블 Top으로 돌아갑니다. 왼쪽 화살표를 따라 내려가는 작업을 구현해주었습니다.
2. 그림 E ~ G : n <= 0이 될 경우 왼쪽 화살표에 대한 함수의 실행을 완료하면 스택에 쌓아두었던 값을 차례로 pop과 동시에 출력하고 위로 올라갑니다.
3. 그림 H : pop과 동시에 위로 올라가고 오른쪽 화살표를 따라 갑니다. n = 1이 되어 recur(1)를 호출하는 것과 같이 1을 push합니다.
4. 그림 I : n = 0이 되어 recur(0)을 호출하여 아무 작업도 일어나지 않고 1을 pop해줍니다.
5. 그림 J ~ L: 4를 pop해주고 오른쪽 화살표를 따라 2와 1를 차례로 push 해줍니다.
6. 그림 M ~ N : 나머지 스택의 원소들도 pop 해줍니다.