재귀와 반복 ; 팩토리얼, 피보나치수

재귀(recursion) :

-> 함수가 자기 자신을 다시 호출하는, 재귀 호출을 이용하는 방법. 불필요한 호출을 하게 되는 경우가 있음.

반복(iteration) :

-> for문, while문, repeat문 등의 반복문을 이용. 재귀보다 수행속도가 빠르고 효율적이지만 문제 자체가 재귀적인 경우에는 프로그램 작성이 어려울 수 있음. but, 대부분의 재귀는 반복문을 사용해 작성할 수 있음.

 

 

 

 

 

 

1. 팩토리얼 함수

- 반복적 정의와 프로그램

n!  =  1                                                                if  n  =  0      n!  =  n x ( n - 1 ) x ( n - 2 ) x  ··· x 1          if  n  >  0

 

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

 

-> 알고리즘 복잡도 분석

- 공간복잡도

: 변수 n, i, fact 총 3개의 변수가 필요하므로 S_I(n) = 3 ∈ θ(1).

 

- 시간복잡도

: 파라미터값이 n일 때 시행되는 곱셈의 수를 계산해 구한다. for문이 n번 시행되므로 T_I(n) = n ∈ θ(n)

 

 

 

- 재귀적 정의와 프로그램

n!  =  1                                     if   n  =  0     n! = n x ( n - 1 )                     if   n  >  0

int factorial(int n){
	if ( n == 0 ) return 1;
	else return ( n * factorial(n-1) );
}

 

-> 알고리즘 복잡도 분석

- 공간복잡도

: 재귀 호출될 때마다 시스템 스택에 활성레코드가 저장된다. 활성레코드는 지역 변수와 파라미터 값들, 리턴 주소 등을 저장. 최대 n+r(임의의 상수 r)만큼 재귀 호출을 시행하므로 S_R(n) ∈ θ(n)

factorial(3) 재귀 호출 중 시스템 스택의 변화 예시

- 시간복잡도

: 파라미터값이 n일 때 시행되는 곱셈의 수를 계산해 구한다.  n이 0일 때는 바로 1이 리턴되므로 곱셈의 수는 0, T_R(0) = 0. 그 외의 n에 대해서는 T_R(n) = 1 + T_R(n-1)를 만족하므로 점화식을 풀어서 구하면 T_R(n) ∈ θ(n)

 

 

 

 

 

 

 

2. 피보나치수

- 피보나치수(재귀적 정의)

F0 = 0, F1 = 1       Fn = Fn-1 + Fn-2       if   n>=2

 

- 재귀 알고리즘

int fib(int n) {
	if ( n == 0 ) return 0;
	if ( n == 1 ) return 1;
	return (fib(n-1) + fib(n-2));
}

fib(6) 재귀 호출 시뮬레이션. 

 

-> 알고리즘 복잡도 분석

 

- 시간 복잡도

: 정수 덧셈의 횟수를 계산해 구한다. n이 0이거나 1일 때는 바로 정수값이 리턴되므로 덧셈 횟수는 0이다. 그 외의 경우에는 이전 단계에서의 덧셈 횟수에 1을 더한 값이 된다. 점화식을 풀면, T_R(n) = F_n+1 - 1라는 식이 나오며 이를 차수표기법으로 표현하면 O(cⁿ)의 값을 가진다.

 

TR(n) = 0, if n = 0 or 1          TR(n) = TR(n-1)  + TR(n-2) + 1, if n>=2

 

 

- 공간 복잡도

: 재귀 호출로 인한 시스템 스택 공간이 추가적으로 요구된다. 팩토리얼 함수의 재귀호출시 상황과 유사하다. S_R(n) = n ∈ θ(n)

 

 

 

- 반복 알고리즘

int fib_iter(int n ){
	if (n==0 or n==1) return n;
    	else {
    		int i, fn, fn1=1, fn2=0;
            	for(i=2; i<=n; i++){
            		fn = fn1+fn2;
                	fn2 = fn1;
                	fn1 = fn;
            	}
            	return fn;
        }
}

 

-> 알고리즘 복잡도 분석

- 시간 복잡도

: 기본연산인 정수 덧셈의 횟수는 n-1번 시행되는 for문 속에 하나 존재하기 때문에 T_I(n) = n-1 ∈ θ(n)

 

- 공간 복잡도

: 변수는 n, i, fn, fn1, fn2 로 총 5개이므로 S_I(n) = 5 ∈ θ(n)