CHAP 2: 순환 (Recursion)
순환 (recursion) 이란? 알고리즘이나함수가수행도중에자기자신을다시호출하여문제를해결하는기법 정의자체가순환적으로 되어있는경우에적합한방법
순환 (recursion) 의예 팩토리얼값구하기 피보나치수열 1 n! n*( n 1)! fib( n) 0 1 fib( n 2) n n 0 ` 1 fib( n 1) if n 0 if n 1 otherwise 이항계수 n C k n1 C 1 k1 n1 C k n 0 or n otherwise k 하노이의탑
팩토리얼프로그래밍 #1 팩토리얼의정의 1 n! n*( n 1)! n 0 n 1 팩토리얼프로그래밍 #1: 위의정의대로구현 (n-1)! 팩토리얼을구하는서브함수 factorial_n_1 를따로제작 int factorial(int n) if( n<= 1 ) return(1); else return (n * factorial_n_1(n-1) );
팩토리얼프로그래밍 #2 팩토리얼프로그래밍 #2: (n-1)! 팩토리얼을현재작성중인함수를다시호출하여계산 ( 순환호출 ) int factorial(int n) if( n <= 1 ) return(1); else return (n * factorial(n-1) ); 3! 은? 3! 를계산하려면 3! = 3*2! 2! 를계산하려면 2! = 2*1! 1! 은 1 3! 는? 2! 는? 1! 는? 6 2 1
순환호출순서 팩토리얼함수의호출순서 factorial(5) = 5 * factorial(4) = 5 * 4 * factorial(3) = 5 * 4 * 3 * factorial(2) = 5 * 4 * 3 * 2 * factorial(1) = 5 * 4 * 3 * 2 * 1 = 120 4 3 factorial(3) if( 3 <= 1 ) return 1; else return (3 * factorial(3-1) ); factorial(2) if( 2 <= 1 ) return 1; else return (2 * factorial(2-1) ); factorial(1) if( 1 <= 1 ) return 1;... 1 2
순환알고리즘의구조 순환알고리즘은다음과같은부분들을포함한다. 순환호출을하는부분 순환호출을멈추는부분 int factorial(int n) if( n <= 1 ) return 1 순환을멈추는부분 else return n * factorial(n-1); 순환호출을하는부분 만약순환호출을멈추는부분이없다면?. 시스템오류가발생할때까지무한정호출하게된다.
순환 <-> 반복 컴퓨터에서의되풀이 순환 (recursion): 순환호출이용 반복 (iteration): for 나 while 을이용한반복 대부분의순환은반복으로바꾸어작성할수있다. 순환 순환적인문제에서는 자연스러운방법 함수호출의오버헤드 1!=1 2!=2 3!=6 3! 를계산하려면 3! = 3*2! 2! 를계산하려면 2! = 2*1! 1! 은 1 반복 수행속도가빠르다. 2! 는? 1! 는? 순환적인문제에대해서는프로그램작성이아주 2 1 어려울수도있다.
팩토리얼의반복적구현 n! n*( n 1 1)*( n 2)* *1 n 1 n 2 int factorial_iter(int n) int k, v=1; for(k=n; k>0; k--) v = v*k; return(v);
거듭제곱값프로그래밍 #1 순환적인방법이반복적인방법보다더효율적인예 숫자 x 의 n 제곱값을구하는문제 : x n 반복적인방법 double slow_power(double x, int n) int i; double r = 1.0; for(i=0; i<n; i++) r = r * x; return(r);
거듭제곱값프로그래밍 #2 순환적인방법 power(x, n) if n=0 then return 1; else if n이짝수 then return power(x 2, n/2); else if n이홀수 then return x*power(x 2, (n-1)/2);
거듭제곱값프로그래밍 #2 순환적인방법
거듭제곱값프로그래밍 #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);
거듭제곱값프로그래밍분석 순환적인방법의시간복잡도 만약 n 이 2 의제곱이라고가정하면다음과같이문제의크기가줄어든다. n n 1 2 1 2 2 2 2 2 0 반복적인방법과순환적인방법의비교 반복적인함수 slow_power 순환적인함수 power 시간복잡도 O(n) O(log(n)) 실제수행속도 7.17초 0.47초
거듭제곱값프로그래밍 #3 효율적인반복적알고리즘구현 double power_iter(double x, int n) int odd_value = 1; while(n > 1) if( n%2==0 ) x = x * x; n = n / 2; else odd_value *= x; x = x * x; n = (n-1) / 2; return(odd_value * x);
피보나치수열의계산 #1 순환호출을사용하면비효율적인예 피보나치수열 0,1,1,2,3,5,8,13,21, 0 fib( n) 1 fib( n 2) fib( n 1) n 0 n 1 otherwise 순환적인구현 int fib(int n) if( n==0 ) return 0; if( n==1 ) return 1; return (fib(n-1) + fib(n-2));
피보나치수열의계산 #1 순환호출을사용했을경우의비효율성 같은항이중복해서계산됨 예를들어 fib(6) 을호출하게되면 fib(2) 이 5 번이나중복되어서계산됨 이러한현상은 n 이커지면더심해짐 fib(6) fib(4) fib(5) fib(2) fib(3) fib(3) fib(4) fib(0) fib(1) fib(1) fib(2) fib(1) fib(2) fib(2) fib(3) fib(1) fib(2)
피보나치수열의반복구현 반복구조를사용한구현 int fib_iter(int n) if( n < 2 ) return n; 0 fib( n) 1 fib( n 2) fib( n 1) n 0 n 1 otherwise int i, fib_n, fib_n_1=1, fib_n_2=0; for(i=2;i<=n;i++) fib_n = fib_n_2 + fib_n_1; fib_n_2 = fib_n_1; fib_n_1 = fib_n; return fib_n;
피보나치수열의효율적인순환호출 효율적인순환구현 int fib_tail_recursion(int n, int fib_n_1, int fib_n_2) if( n < 2 ) return n; int fib_n = fib_n_1 + fib_n_2; return fib_tail_recursion(n-1, fib_n, fib_n_1); 0 fib( n) 1 fib( n 2) fib( n 1) n 0 n 1 otherwise // 더욱간단하게정의하면, int fib_tail_recursion(int n, int fib_n_1, int fib_n_2) if( n < 2 ) return n; return fib_tail_recursion(n-1, fib_n_1 + fib_n_2, fib_n_1); fib_tail_recursion(n, 1, 0);
하노이탑문제 문제는막대 A 에쌓여있는원판 n 개를막대 C 로옮기는것이다. 단, 다음의조건을지켜야한다. 한번에하나의원판만이동할수있다 맨위에있는원판만이동할수있다 크기가작은원판위에큰원판이쌓일수없다. 중간의막대를임시적으로이용할수있으나앞의조건들을지켜야한다.
n=3 인경우의해답
일반적인경우에는? n-1 개의원판 1 개의원판 C 를임시버퍼로사용하여 A 에쌓여있는 n-1 개의원판을 B 로옮긴다. A 의가장큰원판을 C 로옮긴다. A 를임시버퍼로사용하여 B 에쌓여있는 n-1 개의원판을 C 로옮긴다.
남아있는문제는? 자, 그러면어떻게 n-1 개의원판을 A 에서 B 로, 또 B 에서 C 로이동하는가? ( 힌트 ) 우리의원래문제가 n 개의원판을 A 에서 C 로옮기는것임을 기억하라. 따라서지금작성하고있는함수의파라미터를 n-1 로바꾸어순환호출하면된다. // 막대 from 에쌓여있는 n 개의원판을막대 tmp 를사용하여막대 to 로옮긴다. void hanoi_tower(int n, char from, char tmp, char to) if (n==1) from 에서 to 로원판을옮긴다. else hanoi_tower(n-1, from, to, tmp); from 에있는한개의원판을 to 로옮긴다. hanoi_tower(n-1, tmp, from, to);
하노이탑최종프로그램 n-1 개의원판을 A 에서 B 로옮기고 n 번째원판을 A 에서 C 로옮긴 다음, n-1 개의원판을 B 에서 C 로옮기면된다. #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); main() hanoi_tower(4, 'A', 'B', 'C');