슬라이드 1

Transcription

1 Recursion SANGJI University KO Kwangman ()

2 1. 개요 재귀 (recursion) 의정의, 순환 정의하고있는개념자체에대한정의내부에자기자신이포함되어있는경우를의미 알고리즘이나함수가수행도중에자기자신을다시호출하여문제를해결하는기법 정의자체가순환적으로되어있는경우에적합한방법 예제 ) 팩토리얼값구하기 피보나치수열 이항계수 하노이의탑 이진탐색 Lec03_Recursion 2

3 재귀적호출 중복적이거나반복적인호출을수행할때자기자신에대한호출이함수자체에포함되어있는것 직접순환 (directed recursion) 함수가직접자신을호출하는경우 간접순환 (indirected recursion) 다른제3의함수를호출하고그함수가다시자신을호출하는경우 재귀의기본아이디어 단계별수행되는함수내부의절차들이매단계에서조건이만족하는경우최종적인문제의해결이마무리될때까지반복되는것 Lec03_Recursion 3

4 2. 재귀응용 : 삼각수 삼각수 (Triangular Numbers) 1 번째단계의값은 1. ( 이전단계가없으므로 ) n > 1 인단계의값, n-1 단계에서의값과 n 단계의합. 1, 1+2=3, 3+3=4, 6+4=10, 10+5=15, Lec03_Recursion 4

5 Loop 를이용한구현 번째삼각수구하기 (n=4 인경우 ) // 루프를이용하여삼각수구하기 int triloop( int n ) { int tot = 0; while ( n > 0 ) { tot = tot + n; // n을 tot 변수에더한다. --n; // 현재열의번호를감소 return tot; Lec03_Recursion 5

6 재귀를이용하여 n 번째삼각수구하기 (n=4 인경우 ) // 재귀적방법을이용한삼각수구하기 int trirec ( int n ) { if ( n == 1 ) return 1; else return ( n + trirec( n-1 ) ); Lec03_Recursion 6

7 3. 재귀응용 : 순차곱셈 순차곱셈 (factorials) 표기법 Lec03_Recursion 7

8 팩토리얼프로그래밍 int factorial(int n) { if( n <= 1 ) return(1); else return (n * factorial(n-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 Lec03_Recursion 8

9 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; Lec03_Recursion 9

10 4. 재귀응용 : 거듭제곱 순환적인방법이반복적인방법보다더효율적인예 숫자 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); Lec03_Recursion 10

11 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); 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); Lec03_Recursion 11

12 피보나치순열 5. 재귀응용 : 피보나치순열 자신의이전이전수와이전수의합으로만들어진수들의집합 4 번째피보나치수가해지는과정 Lec03_Recursion 12

13 순환호출을사용하면비효율적인예 피보나치수열 0,1,1,2,3,5,8,13,21, 순환적인구현 int fib(int n) { if( n==0 ) return 0; if( n==1 ) return 1; return (fib(n-1) + fib(n-2)); Lec03_Recursion 13

14 순환호출을사용했을경우의비효율성 같은항이중복해서계산됨 fib(6) 을호출하게되면 fib(3) 이 4번이나중복되어서계산됨 이러한현상은 n이커지면더심해짐 fib(6) fib(4) fib(5) fib(2) fib(3) fib(3) fib(4) fib(2) fib(3) fib(1) fib(2) fib(1) fib(2) fib(2) fib(3) Lec03_Recursion 14

15 반복구조를사용한구현 fib_iter(int n) { if( n < 2 ) return n; else { int i, tmp, current=1, last=0; for(i=2;i<=n;i++){ tmp = current; current += last; last = tmp; return current; Lec03_Recursion 15

16 순환방법에서주의할점 순환알고리즘은다음과같은부분들을포함한다. 순환호출을하는부분 순환호출을멈추는부분 int factorial(int n) { if( n <= 1 ) return 1 순환을멈추는부분 else return n * factorial(n-1); 순환호출을하는부분 Lec03_Recursion 16

17 컴퓨터에서의되풀이 순환 (recursion): 순환호출이용 반복 (iteration): for나 while을이용한반복 대부분의순환은반복으로바꾸어작성할수있음 순환 순환적인문제에서는자연스러운방법 함수호출의오버헤드 반복 수행속도가빠름 순환적인문제에대해서는프로그램작성이아주어려울수도있음. Lec03_Recursion 17

18 6. 재귀응용 : 하노이탑 하노이의탑 (Tower of Hanoi) 문제 고대인도로부터내려오는수수께끼 가운데구멍이뚤린원판 (disk) 들을현재기둥 (column) 가 에서 다 로이동시키는문제 Lec03_Recursion 18

19 방법 막대가에쌓여있는원판 n개를막대다로이동방법. 한번에하나의원판만이동. 맨위에있는원판만이동. 크기가작은원판위에큰원판이쌓일수없음. 중간의막대를임시적으로이용할수있으나앞의조건을준수. Lec03_Recursion 19

20 Towers of Hanoi in 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'); Lec03_Recursion 20

21 class Hanoi { static int num_disk = 3; Towers of Hanoi in Java public static void main( String[] args ) { movedisk( num_disk, 'A', 'B', 'C' ); // 최초호출 public static void movedisk( int top, char from, char mid, char to ) { if ( top == 1 ) System.out.println( " 원판 1 이기둥 " + from + " 에서기둥 " + to +" 로이동 " ); else { movedisk( top - 1, from, to, mid ); // from 에서 mid 로이동 System.out.println(" 원판 " + top + " 이기둥 " + from + " 에서기둥 " + to +" 로이동 "); movedisk( top - 1, mid, from, to ); // mid 에서 to 로이동 Lec03_Recursion 21