자료구조 - 순환

순환기법이란? 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하는 기법

ex) 주로 이진탐색이나, 영역채색 ps에 많이 사용

 

// 팩토리얼 프로그래밍
#include <cstido>

int factorial(int n){
	printf("factorial(%d)\n",n);
    if (n == 1) {return 1;} // 끝나는 부분이 있어야함
    else { return n * factorial(n-1); }
}

// 팩토리얼 프로그래밍 반복구현

int factorialIter(int n){
	int result = 1;
    for(int k = n; n >0; n--){
    	result = result * k;}
    return result;
}

---

// 거듭제곱 반복문

double power_Itr(dobule x, int n){
    double result = 1.0;
    for(int i = 0; i<n; i++){
    	result = result * x;}
    return result;
}

// 거듭제곱 순환방법

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

---

but : 피보나치 수열과 같이 순환이 비효율적일수있음

// 순환적인 피보나치구현

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

// 피보나치수열 반복적인 방법

int fibIter(int n)
{
	if(n < 2) { return n; }
    else {
    	int temp, current = 1, last = 0;
        for(int i =2; i<=n; i++){
        	temp = current;
            current += last;
            last = temp;
        }
        return current;
}

이를 이용해서 하노이탑 옮기기

#include <cstdio>

void hanoiTower(int n, char from, char temp, char to)
{
	if( n == 1) { printf("원판 1을 %c에서 %c로 옮긴다.\n",from, to);
    else {
    	hanoiTower(n-1, from, to, temp);
        printf("원판 %d를 %c에서 %c로 옮긴다.\n",n, from, to);
        hanoiTower(n-1, temp, from, to);
    }
}

int main()
{
	hanoiTower(4, 'A', 'B', 'C');
    return 0;
}