반응형
순환 : 자기자신을 호출 반드시 멈추는 문장 포함 되야 함
팩토리얼
int factorial(int n)
{
printf("factorial(%d)\n",n);
if( n <= 1 ) return(1);
else return (n * factorial(n-1) );
}factorial(3) 일시 실행결과
factorial(3)
factorial(2)
factorial(1)
여기 실행결과에서 함수가 호출 되는 것에 집중하여라
피보나치 수열
// 1번
int fib(int n)
{
if( n==0 ) return 0;
if( n==1 ) return 1;
return (fib(n-1) + fib(n-2));
}// 2번
int fib_iter(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
int pp = 0;
int p = 1;
int result = 0;
for (int i = 2; i <= n; i++) {
result = p + pp;
pp = p;
p = result;
}
return result;
}둘다 피보나치 수열이다. 1번 함수와 2번 함수의 차이점이 무엇인가?
1번 함수의 경우에는 fib(6)으로 호출하였을 경우 fib(4)가 두 번이나 fib(3)은 세 번이나 계산이 되어 상당히 비효율적이다.
2번 함수는 순환이 아닌 반복을 이용하여 1번보다는 좋은 결과를 얻을 수 있다.
하노이 탑
#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;
}
반복적인 형태로 바꾸기 어려운 순환
// 1
return n * factorial(n - 1);
// 2
return factorial(n - 1) * n;
꼬리 순환(tail recursion)은 1처럼 순환 호출이 순환 함수의 맨 끝에서 이루어지는 형태의 순환이다. 꼬리 순환의 경우, 알고리즘은 쉽게 반복적인 형태로 변환이 가능하다. 그러나, 2와 같은 머리 순환(head recursion)의 경우나 하노이의 탑 문제처럼 여러 군데에서 자기 자신을 호출하는 경우(multi recursion)는 쉽게 반복적인 코드로 바꿀 수 없다. 물론 이런 경우에도 명시적인 스택을 만들어서 순환을 시뮬레이션할 수는 있다. 만약 동일한 알고리즘을 꼬리 순환과 머리 순환 양쪽으로 모두 표현할 수 있다면 당연히 꼬리 순환으로 작성하여야 한다.
관심이 있으신 분들에게 유용한 정보였길 바라며
다음은 2장 퀴즈와 연습문제 해설을 가져오도록 하겠습니다.
반응형