[자료구조] 2. 순환

1. 순환의 개념

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

 ex) 팩토리얼 함수, 피보나치 함수, 이항 계수 계산, 각종 이진트리, 이진탐색, 하노이탑 등.. 

다음은 간단한 팩토리얼 예제다.

int factorial(int n){
	printf("factorial(%d)\n",n);
	if(n<2) 
		return(1);
	else 
		return (n*factorial(n-1));
}

2. 순환과 반복 

순환 : 자기 자신을 다시 호출하여 작업을 수행하는 방식

반복 : 반복시키는 문장을 작성하는 것

순환의 대표적인 예로는 하노이탑이 있다.

다음은 하노이탑 프로그램이다.

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

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