5-2 재귀 알고리즘 분석

 1. 재귀 알고리즘 분석하기 

 

 - recur 함수는 함수안에서 재귀호출 2회 수행

#include <stdio.h>

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

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

 

1.1 하향식 분석 

 

 - 가장 위쪽에 위치한 상자의 함수 호출부터 시작해 계단식으로 자세히 조사 

 - 꼭대기(top)부터 분석

 

 - recur(4)

1) recur(3) 을 실행

2) 4를 출력 

3) recur(2)를 실행

 

1-2 상향식 분석 

 

- 아래쪽부터 쌓아 올리며 분석 

 

recur(1)

1) recur(0) 실행

2) 1 출력

3) recur(-1) 실행

recur(2)

1)recur(1) 실행 

2) 2출력

3) recur(0) 실행

- 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

 

 

2. 재귀 알고리즘의 비재귀적 표현 살펴보기

 

2-1 꼬리 재귀의 제거 

 

 recur(n-2) 

 - 인자로 n-2를 전달하여 recur 함수 호출

 - n값을 n-2로 업데이트하고 함수의 시작지점으로 돌아감

 

//함수 recur(꼬리 재귀를 제거)
void recur(int n) 
{
	Top:
		if(n>0) {
			recur(n-1);
			pritnf("%d\n",n);
			n=n-2;
			goto Top;
		}
}

 

2-2 재귀의 제거 

 

- 변수 n값을 출력하려면 먼저 recur(n-1)를 수행해야함

- n이 4인 경우 재귀호출 recur(3)의 처리가 완료되지 않으면 n값인 '4'를 저장해야 함

- 현재 n값을 '잠시'저장하는 과정 필요 

- recur(n-1)의 처리가 완료된 다음에 n값을 출력할 때는 

 저장했던 n을 꺼내 그 값을 출력 

- 스택을 통해 구현

 

#include <stdio.h>

// 재귀 호출을 제거한 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);
 }

 

recur(4)

1) 4를 스택에 푸시 

2) n값을 하나 줄여 3으로 만듬

3) goto문이 실행되어 Top if로 돌아감

-위 과정 반복하면 스택에 4,3,2,1이 쌓임 

-다음 if문 실행 

4) 스택에서 팝한 값 1을 n에 꺼내 놓음

5) n값 1을 출력

6) n값을 2줄여 -1로 만듬

7) goto문이 실행되어 Top if문으로 돌아감

 

- n이 0이하가 되어 스택이 텅비면 두 if문 모두 실행되지 않고 종료 

 

 

3. 메모이제이션 알아보기 

 

- recur 함수를 실행하는 과정에서는 여러 번 반복해 같은 계산 수행

 

- 메모제이션(memoization)

 -> 어떤 문제에 대한 해답을 얻으면 그것을 메모해둠

 -> 중복계산을 제거하여 실행속도를 빠르게 해줌

 -> ex) recur(3)은 1,2,3,1을 출력하므로 해당 문자열을 메모 

 

#include <stdio.h>
#include <string.h>

//재귀 함수 recur를 메모제이션으로 구현

static char memo[128][1024]; //메모용 문자열 배열

//메모제이션을 도입한 recur 함수 
void recur(int n) {
	if(memo[n+1][0])!='\0') //메모를 이미 한경우 
		printf("%s",memo[n+1]); //메모 출력 
	else { //메모 x인경우  
		if(n>0) {
			recur(n-1);
			printf("%d\n",n);
			recur(n-2);
			sprintf(memo[n+1],"%s%d\n%s",memo[n],n,memo[n-1]);  //출력한 문자열을 배열 요소 memo[n+1]에 메모  
		}
		else {
			strcpy(memo[n+1],"");
		}
	} 
}

 

- 저장을 위한 2차원 배열 memo 미리 지정

- recur 함수가 n에게 받는 인숫값과 메모용 memo 배열의 인덱스는 1씩 어긋남

recur(-1)의 실행 결과 (출력할 문자열) "" memo[0]

recur(0)의 실행 결과 (출력할 문자열) "" memo[1]

recur(1)의 실행 결과 (출력할 문자열) "1" memo[2]

recur(2)의 실행 결과 (출력할 문자열) "1\n2" memo[3]

 

- 메모를 이미 한 경우 

 n에 대해 이미 메모한 경우에는 해당 메모의 내용 memo[n+1]을 그대로 화면에 출력

 

- 메모를 하지 않은 경우 

n이 0보다 클때:

 원래의 recur와 같은 처리를 수행

 출력한 문자열을 배열 요소 memo[n+1]에 메모

 

n이 0보다 크지 않을 때 :

 n은 0 아니면 -1 

 빈 문자열 ""을 메모