재귀함수를 이용한 팩토리얼 구하기, 최대공약수 구하기

재귀함수란 함수가 자신을 호출하는것..

자신이 자신을 호출할 때는 같은 형식이 반복되므로 while문과 같은 반복문이 된다.

그래서 반드시 재귀를 끝내는 조건이 필요하다는 것이다.!

예를 들어 5!를 구해보자.. 단순 for문으로 했을 시

int fact=1;

for(int i=1;i<5;i++)

{

fact*=i;

cout << i << "!=" << fact << endl;

}

fact*=1;

1*=1; // fact=1;

1*=2; // fact=2;

2*=3 // fact=6;

이런식으로 가는데...

이것을 재귀함수로 구현하게 된다면..

int fact(int n)

{
    if(n==1 || n==0)

{        

return 1;

}

else

return n*fact(n-1);

}

이렇게 계속 함수를 자기함수를 호출하게 하여 만들고..

 

최대공약수의 경우 쉽게 구하기 위해 유클리드 호제법을 이용한다.(뭐지 저이름..)

작은 수쪽은 그대로, 근 수쪽은 큰 수 - 작은 수로 만들어 두 수가 같아질 때까지 반복한다.

즉..(15, 80) 15 < 80 이므로(15, 80-15) 이런식으로..하고 다시 15 < 65이므로..

계속 반복을 하다가 보면 같아진다..만약 (10,5) 이면..10>5 이미로..(10-5, 5)이렇게 하고..숫자 5가 같아지므로..(5,5)다

int gcd(int m, int c)
{
 if(m>c)
 {
  return gcd(m-c,c);
 }
 else if(m==c)
 {
  return m; //반드시 필요한 재귀를 끝내는 조건이다!
 }
 
 else {
  return gcd(m,c-m);
 }
 
}

이런식으로 한다..

 

---

요즘 쓸떄없이 피곤해서..여기까지.....?!