Recursion SANGJI University KO Kwangman (kkman@sangji.ac.kr)

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

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

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

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

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

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

팩토리얼 프로그래밍 팩토리얼 함수의 호출 순서 int factorial(int n) { 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 int factorial(int n) { if( n <= 1 ) return(1); else return (n * factorial(n-1) ); }

else return (2 * factorial(2-1) ); } if( 2 <= 1 ) return 1;     else return (2 * factorial(2-1) ); } factorial(1) { if( 1 <= 1 ) return 1; ..... ① ② ③ ④ factorial(3) { if( 3 <= 1 ) return 1;     else return (3 * factorial(3-1) );

4. 재귀응용 : 거듭제곱 순환적인 방법이 반복적인 방법보다 더 효율적인 예 숫자 x의 n제곱값을 구하는 문제: xn double slow_power(double x, int n) { int i; double r = 1.0; for(i=0; i<n; i++) r = r * x; return(r); }

power(x, n) if n=0 then return 1; else if n이 짝수 then return power(x2,n/2); else if n이 홀수 then return x*power(x2, (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); }

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

순환 호출을 사용하면 비효율적인 예 피보나치 수열 순환적인 구현 int fib(int n) { 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)); }

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

반복 구조를 사용한 구현 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;

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

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

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

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

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');

Towers of Hanoi in Java class Hanoi { static int num_disk = 3; 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로 이동