[자료구조] - 순환, 반복

순환이란

어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법

장점 : 알고리즘을 훨씬 명확하고 간결하게 나타냄

팩토리얼

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

//시간 복잡도 : 순환 호출이 n번 발생하므로 O(n)

메모리 생성 순서와 죽는 순서는 반대

시스템 스택의 변화
f(3) -> f(2)호출 -> f(1)호출 -> 1반환 -> 2x1반환 -> 3x2반환

주의 사항 : 순환 호출을 멈추는 부분이 없다면 무한 호출로 오류 발생

좋은 방법이지만 위험성이 있고 중복호출로 인한 메모리 부족 발생

따라서 반복으로 대체가능!

int factorial_iter(int n)
{
    int i, result = 1;
    for(i=1; i<=n; i++)
        result = result * i;
    return(result);
}

//시간복잡도 : for문을 사용하여 n번 반복 하므로 O(n)

거듭제곱

반복

double slow_power(double x, int n)
{
	int i;
	double result = 1.0;

	for (i = 0; i<n; i++)
		result = result * x;			// 반복
	return(result);
}

시간 복잡도 : for문에서 n번 반복 함으로 O(n);

순환

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);
}

순환 호출 할때 마다 n의 크기
n제곱 -> n/2제곱 -> n/4제곱 가 줄어든다 따라서 시간복잡도 : O(logn)

피보나치 수열

순환

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

호출을 할때마다 중복 메모리가 높아지고 호출할때마다
$2^0$ -> $2^1$ -> $2^2$ ... 결국 O($2^n$)이다.

반복

int fib_iter(int n)         
{
    if (n == 0) return 0;     // n이 0과 1일때 리턴값 반환
    if (n == 1) return 1;
        
    int pp = 0;	
    int p = 1;
    int result = 0;
        
    for (int i = 2; i <= n; i++) {  // i는 2부터 i 까지 반복
        result = p + pp;
        pp = p;
        p = result;
    }
    return result;              // 리턴값 반환
} 

// for문 안에서 n번 반복 : O(n)

하노이탑

먼저 하노이탑의 원리를 의사코드로 한번 적어보자

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로 옮긴다.
     }
 }
   

위의 의사코드는 하노이탑 문제를 해결하는 방법에 대해 적혀있다.
저 의사코드를 프로그램밍 언어로 바꾸기만 하면 된다.

// from : 출발 , to : 도착

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("원판 %d을 %c에서 %c으로 옮긴다.\n", n, from, to);			
		hanoi_tower(n - 1, tmp, from, to);					
	}
}

나머지는 디버깅을 하면서 프로그램의 동작을 확인해보자.