2. 재귀를 활용한 계산

2. 거듭 제곱 값 계산

<프로그램 2.2.1> 반복적인 거듭제곱 계산 프로그램

int slow_power(double x, int n){
    double r = 1.0;
    for(int i=0;i<n;i++){
    	r = r*x;
    }
    return r;
} // -> O(n)

<알고리즘 2.2.1> 순환적인 거듭제곱 계산

power(x,n)

if n=0
	return 1;
else if n이 짝수
	then return power(x^2,n/2);
else if n이 홀수
	then return x * power(x^2,(n-1)/2);
    
 (1) n이 짝수인 경우
 power(x,n) = power(x^2, n/2)
 			= (x^2)^(n/2)
            = x^2^(n/2)
            = x^n
 (2) n이 홀수인 경우
 power(x,n) = x * power(x^2,(n-1)/2)
 			= x*(x^2)^((n-1)/2)
            = x * x^(n-1)
            = x^n

<프로그램 2.2.2> 순환적인 거듭제곱 계산 프로그램

double power(double x, int n){
	if(n == 0) return 1;
    else if(n%2 == 0) return power(x*x, n/2);
    else return x*power(x*x,(n-1)/2);
} // -> O(logn)

-> 반복적인 거듭제급 계산보다 순환적인 거듭제곱 계산이 더 빠름, 순환을 호출할 때마다 문제의 크기가 약 절반으로 줄어들기 때문

Quiz

1. power(2,6)과 같이 호출하였을 경우에 호출 체인을 그리시오

power(2,6) = power(4, 3) 
		   = 4 * power (16, 1) 
           = 4 * 16 * power(256 , 0)
           = 4 * 16 * 1
           = 4 * 16
           = 64

1. 거듭제곱 값을 계산하는 함수를 다음의 순환적인 정의를 이용하여 작성하면 실행시간이 줄어드는가?
   xn={1ifn=0x∗x(n−1)ifn>0​

double power(double x, int n){
    if(n == 0)
        return 1;
    else
        return x * power(x, n - 1);
}

실행시간은 줄어들지 않는다 -> O(n)

3. 피보나치 수열의 계산

fib(n)=⎩⎪⎪⎨⎪⎪⎧​0n=01n=1fib(n−2)+fib(n−1)otherwise​

-> 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

<프로그램 2.3.1> 순환적인 피보나치 수열 계산 프로그램

#include <stdio.h>

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

fib(6) = fib(4) + fib(5)
	   = fib(2) + fib(3) + fib(3) + fib(4)
       = fib(0) + fib(1) + fib(1) + fib(2) + fib(1) + fib(2) + fib(2) + fib(3)
       = 0 + 1 + 1 + fib(0) + fib(1) + 1 + fib(0) + fib(1) + fib(0) + fib(1) + fib(1) + fib(2)
       = 0 + 1 + 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 + 1 + fib(0) + fib(1)
       = 0 + 1 + 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 + 1 + 0 + 1
       = 8

• 매우 이해하기 쉽지만 매우 비효율적, fib(6)으로 호출하였을 경우 fib(4)가 2번, fib(3)은 3번 계산됨. 이런 현상은 순환 호출이 깊어질수록 점점 심해짐

<프로그램 2.3.2> 반복적인 피보나치 수열 계산 프로그램

int fib_iter(int n){
	int tmp, current =1, last = 0;
    for(int i=2;i<=n;i++){
    	tmp = current;
        current += last;
        last = tmp;
    }
    return current;
}

Quiz

1. fib(7)이 호출되었을 경우에 fib(4)는 몇번이나 중복 계산되는가? 3번 중복 계산됨

fib(7) = fib(5) + fib(6)
	   = fib(3) + fib(4) + fib(4) + fib(5)
       = fib(3) + fib(4) + fib(4) + fib(3) + fib(4)

1. 반복적인 피보나치 수열 계산 함수의 시간복잡도? -> O(n)
2. 순환적인 피보나치 수열 계산 함수의 대략적인 시간복잡도를 추리할 수 있겠는가? 하나의 함수 호출이 두 개의 함수 호출로 나누어진다는 점에 착안하라 -> O(2n)

4. 하노이탑 문제

하노이탑 조건

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

n개의 원판을 가지는 하노이탐 문제의 해답
1. A의 n-1개 원판을 B로 옮긴다.
2. A의 제일 밑에 있는 원판을 C로 옮긴다.
3. B의 n-1개 원판을 C로 옮긴다.

// 막대 from에 쌓여 있는 n개의 원찬을 막대 tmp를 사용하여 막대 to로 옮긴다.
void hanoi_tower(int n, char from, char tmp, char to){
	if(n == 1){
    	from에서 to로 원판을 옮긴다.
    }else{
    	1. from의 맨 밑에 있는 원판을 제외한 나머지 원판들을 tmp로 옮긴다.
        2. from에 있는 한 개의 원판을 to로 옮긴다.
        3. tmp의 원판들을 to로 옮긴다.
    }
}

• 1, 3은 막대 위치만 달라졌을 뿐 원래 문제의 축소된 형태라는 것을 발견할 수 있음. 1은 to를 사용하여 from에서 tmp로 n-1개의 원판을 이동하는 문제이고, 3은 from을 사용하여 tmp에서 to로 n-1개의 원판을 이동하는 문제

// 막대 from에 쌓여 있는 n개의 원찬을 막대 tmp를 사용하여 막대 to로 옮긴다.
void hanoi_tower(int n, char from, char tmp, char to){
	if(n == 1){
    	from에서 to로 원판을 옮긴다.
    }else{
    	hanoi_tower(n-1, from, to, tmp); // to를 사용하여 from에서 tmp로 n-1개 원판을 이동
        from에 있는 한 개의 원판을 to로 옮긴다.
        hanoi_tower(n-1, tmp, from, to); // from을 사용하여 tmp에서 to로 n-1개 원판을 이동
    }
}

<프로그램 2.4.1> 하노이탑 문제 프로그램

#include <stdio.h>
void hanoi_tower(int n, char from, char tmp, char to){
	if(n == 1){
    	printf("원판 1을 %c에서 %c으로 옮긴다.\n",from, to);
    }else{
    	hanoi_tower(n-1, from, to, tmp);
        printf("원판 1을 %c에서 %c으로 옮긴다.\n",from, to);
		hanoi_tower(n-1, tmp, from, to);
    }
}

main(){
	hanoi_tower(4,'A','B','C');
}

- 반복적인 형태로 바꾸기 어려운 순환

다음 팩토리얼 예제에서 차이점

1. return n * factorial(n-1);
2. return factorial(n-1) * n;

• 꼬리 순환(tail recursion)은 1처럼 순환 호출이 순환 함수의 맨 끝에서 이루어지는 형태의 순환, 이 경우 알고리즘은 쉽게 반복적인 현태로 변환이 가능
• 머리 순환(head recursion)인 2나 하노이탑 문제처럼 여러 군데에서 자기자신을 호출하는 경우(multi recursion)는 쉽게 반복적인 코드로 바꿀 수 없음

Quiz

1. 순환을 사용하는 방법에 대한 설명 중 잘못된 것은? -> 3
   (1) 순환적으로 정의된 문제에 적합하다.
   (2) 반복을 이용하는 것보다 효율적이다.
   (3) 간접적으로 시스템 스택이 사용된다.
   (4) 순환이 될 때마다 문제의 크기는 작아진다.