순환(재귀)과 반복

순환(recursion)이란

 알고리즘이나 함수가 자기 자신을 다시 호출하여 문제를 해결하는 기법이다.

문제 정의 자체가 순환적으로 되어 있는 경우에 적합하다.

예) 팩토리얼, 피보나치 수열, 하노이의 탑, 이진탐색 등

 

반복이란

 for문, while문등 흔히 쓰는 반복문을 통한 알고리즘이다.

순환에 비해 수행속도가 빠르지만 순환적인 문제는 알고리즘이 매우 복잡해질 수 있다.

수행속도가 빠르다고 문제해결 속도가 빠른 것은 아니다.

순환으로 10번만에 할 계산은 반복으론 10000번을 해야할 수도 있다.

예제1 팩토리얼

 순환

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

반복

int factorial_iter(int n)
{
int k, v=1;
for(k=n; k>0; k--)
v = v*k;
return(v);
}

에제2 거듭제곱

 순환

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

반복

double slow_power(double x, int n)
{
int i;
double r = 1.0;
for(i=0; i<n; i++)
r = r * x;
return(r);
}