알고리즘 : recursion 1

Recursion이 무한 루프에 빠지지 않기 위해서는

Base case

Recursive case

가 존재해야 한다

Recursive case에서 recursion을 반복 -> Base case로 수렴해야 함.

그렇지 않은 경우가 있기 때문에 Base case가 '존재'한다고 무한 루프가 발생하지 않는 것은 아니다.

최대공약수 구하기 : 유클리드 호제법

m>=인 두 양수 정수 m과 n에 대해서 m이 n의 배수이면 gcd(m,,n)=n이고, 그렇지 않으면 gcd(m,n)=gcd(n,m%n)이다.

int gcd(int a,int b)

{ //반복문을 이용한 방법

int mod = a % b;

while(mod > 0)

{

a = b;

b = mod;

mod = a % b;

}

return b;

}

int gcd2(int a,int b)

{ //재귀 함수형

if(m<n){

int tmp=m;

m=n;

n=tmp;

}

if( a % b == 0 )

return b;

else

return gcd2(b, a % b);

}

int gcd3(int a, int b)

{ //삼항 연산자 축약형

return (a % b == 0 ? b : gcd3(b,a%b));

}




좀더 단순한 버전

gcd(p,q) = p //if q=0

gcd(q,p%q) //otherwise.

int gcd (int p, int q){

if(q==0)

return p;

else

return gcd(q,p%q);

}