[자료구조] : "재귀 알고리즘 분석" (C)

출처 | DO IT C언어 자료구조 입문편

이번 시간에는 알고리즘을 분석하기 위해 하향식 분석 / 상향식 분석을 살펴보겠다.

다음 예제를 보자.

#include <Stdio.h>

void recur(int n)
{
	if (n > 0)
	{
		recur(n - 1);
		printf("%d\n", n);
		recur(n - 2);
	}
		


}

int main()
{
	int x;
	printf("정수를 입력허세요 : ");
	scanf_s("%d", &x);
	recur(x);

	return 0;
}

• recur 함수는 factorial 함수나 gcd 함수와 달리 함수 안에서 재귀 호출을 2번 실행한다.

<결과>

recur 하향식 분석

• 가장 위쪽에 위치한 상자의 함수 호출부터 시작해 계단식으로 자세히 조사해 가는 분석 기법을 하향식 분석이라고 한다.

1. recur(3)을 실행한다.
2. 4를 출력한다.
3. recur(2)을 실행한다.

- 2에서 4를 출력하는 것은 1의 recur(3)의 실행이 완료된 다음이다.
- recur(3)부터 먼저 조사해야된다.

• recur(3)의 호출 이후에 어떤 과정을 거치게 되는지는 왼쪽 화살표를 따라가면 된다.

• 왼쪽 화살표를 따라 하나 아래 상자로 이동하고, 다시 원래의 상자로 돌아오면 ■ 안의 값을 출력하고 이어서 오른쪽 화살표를 따라 한 칸 아래 상자로 이동한다.

• 이 작업이 완료 되어야 한 칸 위의 상자로 이동 가능하다.

• recur(3)을 호출하면 호출한 상자로 돌아가기 위해 많은 단계를 거쳐야한다.

상향식 분석

• 아래쪽부터 쌓아 올리며 분석하는 방법이 상향식 분석이다.
• recur 함수는 n이 양수일 때만 실행하는 조건 / 먼저 recur(1)을 생각해야된다.

1. recur(0)을 실행한다.
2. 1를 출력한다.
3. recur(-1)을 실행한다.
4. reucur(0)과 recur(-1)은 출력할 내용이 없다.

1. recur(2)에 대해 생각해보자.
2. recur(1)을 실행한다.
3. 2를 출력한다.
4. recur(0)을 실행한다.

= recur(1)은 1을 출력하고 / recur(0)은 출력할 내용이 없다. 
= 전체과정을 거치면 1과 2를 출력한다.
= recur(4)까지 쌓아 올려 설명하면 

#recur(-1), recur(0)은 아무것도 하지 않음 
recur(1) : recur(0) 1 recur(-1) :  1
recur(2) : recur(1) 2 recur(0) : 1 2
recur(3) : recur(2) 3 recur(1) : 1 2 3 1 
recur(4) : recur(3) 4 recur(2) : 1 2 3 1 4 1 2

재귀 알고리즘의 비재귀적 표현으로 구현해보자.

1. 꼬리 재귀의 제거를 필수적으로 해야된다. 
2. recur(n-2)라는 말은 인자로 n-2를 전달하여 recur함수를 호출한다는 의미다. 
3. n의 값을 n-2로 업데이트하고 함수의 시작 지점으로 돌아간다.

<코드>

void recur(int n)
{
Top:

	if (n > 0)
	{
		recur(n - 1);
		printf("%d\n", n);
		n = n - 2;
		goto Top;
	}


}

1. 변수 n값을 출력하기 전에 recur(n-1)을 먼저 수행해야 한다.

2. 예를 들어, n이 4인 경우 재귀 호출 recur(3)의 처리가 완료되지 않으면 n의 값인 4를 저장해야 한다.

3. n의 값을 n-1로 업데이트 하고 함수의 시작 지점으로 돌아간다.

4. 현재 n의 값을 잠시 저장한다.

5. 저장했던 n을 다시 꺼내서 그 값을 출력한다.

• 핵심 아이디어 : 값을 잠시 저장해야 된다는 사실 & stack 연관성 ↑

스택을 사용하여 비재귀적으로 구현한 recur

void recur(int n)
{
	IntStack stk;
	Initialize(&stk, 100);
Top:
	if (n > 0)
	{
		Push(&stk, n); ....1
		n = n - 1; ....2
		goto Top; ....3
	}
	if (!IsEmpty(&stk))
	{
		Pop(&stk, &n); ....4
		printf("%d\n", n); ....5
		n = n - 2; ....6
		goto Top; ....7
	}
	
	Terminate(&stk);
}

• recur(4)를 호출한 과정은 이와 같다.

1. 4를 스택에 푸시한다.
2. n의 값을 하나 줄여 3으로 만든다.
3. goto문이 실행되어 레이블 Top으로 돌아간다.
4. 3은 0보다 크기 때문에 첫 번째 if문이 실행된다. -> 스택에 4, 3 ,2 ,1 쌓인다.
5. 마지막으로 스택에 1을 쌓은 뒤 0이 되고 Top으로 돌아가서 맨 앞 if문을 실행한다.
6. n 값이 0이므로 첫 번째 if문은 지나가고 
7. 다음의 if문에 의해 스택에서 팝한 값 1을 n에 꺼내 놓는다.