순환

1. 순환이란?

• 순환(recursion), 또는 재귀 호출이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다.

• 예를 들어 정수의 팩토리얼(factorial)은 다음과 같이 정의된다.
  

• 위의 정의에서 factorial(n!)을 정의하는데 다시 factorial(n-1)!이 사용된 것에 주목하자. 이러한 정의를 순환적이라 한다.

#include<stdio.h>
int factorial(int n){//순환적인 팩토리얼 계산 함수
	if(n==1){// n==1일 경우  
		return 1;
	}
	else{//n>1일 경우  
		return (n*factorial(n-1));
	}
}	
int main(){
	printf("5! : %d",factorial(5));
}

2. 반복적인 팩토리얼 계산 함수

• 아래 예제를 사용하면 더 빠르게 순환을 사용할 수 있다.

#include<stdio.h>
int factorial_iter(int n){
	int k, result=1;
	for(k=n;k>0;k--){
		result *= k;
	}
	return result;
}	
int main(){
	printf("5! : %d",factorial_iter(5));
}

3. 순환 알고리즘의 성능

• 위의 팩토리얼 예제에서 반복과 순환의 성능을 분석하여 보자. 반복 알고리즘의 시간 복잡도는 어떻게 될까? for를 사용하여 n번 반복하므로 시간 복잡도는 O(n)이다.
• 팩토리얼의 순환 알고리즘 구현의 시간 복잡도는 순환에서는 한번 호출할 때마다 1번의 곱셈이 수행되고 전체 순환 호출이 n번 일어나므로 O(n)이다.

4. 피보나치수열의 계산

• 피보나치수열의 정의
  

int fib(int n){//피보나치 수열의 순환적 호출
	if(n==0)
		return 0;
	if(n==1)
		return 1;
	return (fib(n-1)+fib(n-2));
}

• 위의 함수는 단순하고 이해하기 쉽게 구현되었지만, 매우 비효율적이다. 순환을 반복할수록 n이 커지게 되면 엄청난 순환호출이 필요하게 된다.

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

5. 하노이탑

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