재귀함수 문제(반복문 치환)

팩토리얼 

재귀함수

int fac(int num)

{

if(num <= 1)

return 1;

return n * fac(num - 1);

}

반복문

int fac(int num)

{

if(num <= 1)

return 1;

int current = 1;

for(int i = 2; i <= num; ++i)

{

current = current * i;

}

}

피보나치수열

재귀함수

int fibona(int num)

{

if(num == 0)

return 0;

if(num == 1)

return 1;

return fibona(n - 1) + finoba(n - 2);

}

반복문

if (num < 2)

return 1;

int prev = 1;

int current = 1;

for (int i = 3; i <= num; ++i)

{

int temp = prev;

prev = current;

current = temp + current;

}

return current;

최대공약수 찾기(유클리드 기법)

간단한 GCD(최대공약수)를 구하는 코드입니다.

여기에 이용되는 방법 중 하나가, 유클리드 호제법이라는 방법입니다.

A, B가 있을 때((A > B)라고 가정) A를 B로 나눴을 때 나눠지면 B가 최대 공약수입니다.

하지만 나누어 떨어지지 않으면 A를 B로 B를 A % B로 치환하고서 다시 A % B를 실행합니다.

계속 반복했을 때 A % B = 0이 됐을 때의 B값이 GCD값이 됩니다.

12와 9를 기준으로 보겠습니다.

A % B = 3 입니다.

나누어 떨어지지 않았기 때문에 A = B, 즉 9가 되고 B = A%B, 즉 3이 됩니다.

9와 3을 가지고 다시 돌립니다.

A%B = 0

그럼 여기서 나오는 3(B의값)이 최대공약수라는 것을 알 수 있습니다.

최대공약수가 쓰이는 부분은 많지만 가장 기본적인 경우는 분수의 연산시에 필요합니다.

15 / 20 은 3 / 4로도 표현될 수 있습니다.

이 유클리드 호제법을 이용한 GCD 구하는 코드는 다음과 같습니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

int Euclid(int a, int b) {       if (a >= b)     {         if (a%b == 0)             return b;         else             return Euclid(b, a%b);     }     else     {         if (b%a == 0)             return a;         else             return Euclid(a, b%a);     } }

a % b가 0이 되면 그것을 리턴해주고

나누어 떨어지지 않으면 다시 Euclid 함수를 호출하는 것입니다.

처음의 if와 else의 쌍은 a가 b보다 클 수도 있고 작을 수도 있기 때문에 추가해 놓았습니다.

이 코드를 없애고 싶으시면 항상 a를 b보다 크게해서 한다거나 하시면 됩니다.

출처: http://psychoria.tistory.com/entry/%EA%B0%84%EB%8B%A8%ED%95%9C-GCD-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Euclid-%ED%98%B8%EC%A0%9C%EB%B2%95 [냉정과 열정사이]

재귀함수

int Eucild(int a, int b)

{

if (a >= b)

{

if (a%b == 0)

return b;

else

return Eucild(b, a%b);

}

else

{

if (b%a == 0)

return a;

else

return Eucild(a, b%a);

}

}

반복문

int Eucild2(int a, int b)

{

int tempA = a;

int tempB = b;

if (a >= b)

{

while (true)

{

if ((tempA % tempB) == 0)

return tempB;

int tempC = tempA;

tempA = tempB;

tempB = tempC% tempB;

}

}

else

{

}

}

하노이탑

재귀함수

void hanoi_tower(int n, char from, char temp, char to)

{

if (n == 1)

{

cout << "원판 1을" << from << "에서" << to << "로 옮김" << endl;

return;

}

hanoi_tower(n - 1, from, to, temp);

cout << n << "번째 원판을" << from << "에서" << to << "로 옮겼습니다" << endl;

hanoi_tower(n - 1, temp, from, to);

}

1 + 2 + 3 + ...+ n까지 더하는 것

재귀함수

int Test(int n)

{

if (n == 1)

return 1;

return n + Test(n - 1);

}

반복문

int sum2(int n)

{

if (n == 1)

return 1;

int current = 1;

for (int i = 2; i <= n; ++i)

{

current += i;

}

return current;

}

1 + 1/2 + 1/3 + 1/4 ....... + 1/n 까지 더한것

재귀함수

float Test(float n)

{

if (n == 1)

return 1;

return (1.0 / n) + Test(n - 1);

}