[자료구조] 순환

🩰 순환 (Recursion) ?

 

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

 

🔑 대표적 예시 : 순환적인 팩토리알 계산 프로그램

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

 

만약, factorial(3)을 호출했다면 위 프로그램에서 수행되는 동시에 factorial(2)를 호출한다. 그러면 factorial(2)는 다시 factorial(1)을 호출하게 된다. 이 과정을 살펴보면 다음과 같다.

 

/*
factorial(3)=3*factorial(2)
	    =3*2*factorial(1)
            =3*2*1
            =6
*/

 

🩰 반복 VS 순환

 

• 반복

for이나 while 등의 반복구조로 되풀이 하는 방법

 

🔑 예시 : 순환적인 팩토리알 계산 프로그램

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

 

위의 팩토리알을 계산하는 순환, 반복문의 시간 반복도는 모두 O(n)으로 동일하다. (for문을 사용하여 n번 반복, 한번 순환호출 할 때마다 1번의 곱셈이 수행되고 순환호출은 n번 일어나기 때문) 그러나 순환의 경우 여분의 기억공간이 필요하고 또한 함수를 호출하기 위해서는 함수의 매개변수들을 스택에 저장하는 작업이 필요로 하기 때문에 비효율적이다. 

 

---

 

🔑 거듭제곱 알고리즘

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

 

 

🔑 하노이탑 문제 

n개의 원반을 From에서 To로 옮길때 , 만약 n이 1이면 to로 바로 옮기면 되고 n이 1보다 크면 가장 큰 원반을 제외한 나머지 n-1개의 원반을 tmp에 잠깐 둔뒤 가장 큰 원반을 to에 담고 나머지 tmp에 있던 원반을 to에 담으면 된다 !

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

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