프로그래밍 기초와 실습 Chapter 11 Recursion

Contents Recursive Problem Solving Drawing Patterns on the Screen (Example) String handling Using Recursion (Example) Quick Sort (The Divide-and-Conquer Methodology)

Recursive Problem Solving 재귀호출 어떤 함수가 자기 자신을 호출하는 것 [Ex] #include <stdio.h> void count_down(int n); int main(void) { count_down(10); return 0; } void count_down(int n) if( n ) { printf(“%d ! ”, n); count_down( n – 1 ); else printf(“\nBLAST OFF\n”); 10 ! 9 ! 8 ! 7 ! 6 ! 5 ! 4 ! 3 ! 2 ! 1 ! BLAST OFF

Recursive Problem Solving factorial을 구하는 예제 [Ex] /* Recursive version */ int fact( int n) { if ( n <= 1 ) return 1; else return n * fact ( n - 1 ); } [Ex] /* Iterative version */ int fact( int n ) int result = 1; for ( ; n > 1; --n ) result *= n; return result; What i = fact(3) returns fact ( 3 ) 3 * fact (2 ) 3 * ( 2 * fact ( 1 ) ) 3 * ( 2 * ( 1 ) ) = 6

Recursive Problem Solving 합을 구하는 예제 [Ex] /* Recursive version */ int sum ( int n ) { if ( n <= 1 ) return n; else return ( n + sum ( n – 1 ) ); } [Ex] /* Iterative version */ int sum = 0; while ( n <= 5 ) sum += n; return sum; What sum() returns Function call Value returned sum(1) sum(2) sum(3) sum(4) 1 2 + sum (1) or 2 + 1 3 + sum (2) or 3 + 2 + 1 4 + sum (3) or 4 + 3 + 2 + 1 = 10

Recursive Problem Solving array의 평균을 구하는 예제 [Ex] /* recursion 사용 */ double average(double a[], int n) { if ( n == 1 ) return a[0]; else return ((a[n – 1] + (n – 1 ) * average(a, n – 1 )) /n ); } [Ex] /* 반복문 사용 */ double sum = 0.0; int i; for(i = 0; i < n; ++i) sum += a[i]; return (sum / n);

Drawing Patterns on the Screen 제곱근을 구하는 예제 [Ex] /* Recursive version */ int power ( int x, int n ) { if ( n == 0 ) return 1; else return x * power( x, n – 1 ); } [Ex] /* Iterative version */ int pow = 1; for ( ; n > 0; n--) pow *= x; return pow; return n == 0 ? 1 : x * power (x, n – 1); 와 같다. What power(5, 3) returns power ( 5, 3 ) 5 * power ( 5, 2) 5 * ( 5 * ( power(5, 1) ) ) 5 * ( 5 * ( 5 * (power (5, 0 ) ) ) 5 * ( 5 * ( 5 * ( 1 ) ) ) = 125

Drawing Patterns on the Screen 역순으로 문자를 출력하는 예제 입력 받은 문장의 문자들을 역순으로 출력한다. [Ex] /* Write a line backward. */ #include <stdio.h> void prn_it(void); int main(void) { printf(“Input a line: “); prn_it(); printf(“\n\n”); return 0; } void prn_it(void) char c; if( ( c = getchar() ) != ‘\n’) putchar(c); Input a line: sing a song of sixpence ꎠ ecnepxis fo gnos a gnis

Drawing Patterns on the Screen 역순으로 단어를 출력하는 예제 입력 받은 문장의 단어들을 역순으로 출력한다. #include <ctype.h> #include <stdio.h> #define MAXWORD 100 void prn_it_by_word(void); void get_word(char *); int main(void) { printf("input a line: "); prn_it_by_word(); printf("\n\n"); return 0; } void prn_it_by_word(void) char w[MAXWORD]; get_word(w); if (w[0] != '\n') printf("%s ", w); /* continue… */ get_word로 받아들인 문자가 new line이 아닐 때까지 prn_it_by_word()를 recursive 로 호출 prn_it_by_word()함수를 호출

Drawing Patterns on the Screen 역순으로 단어를 출력하는 예제 void get_word(char *s) { static char c = '\0'; if( c == '\n' ) *s++ = c; else while ( !isspace( c = getchar() ) ) *s = '\0'; } Input a line: deep in the heart of texas ꎠ texas of heart the in deep

String handling Using Recursion 특정 조건에 의해 문자열 출력하는 예제 [Ex] #include <stdio.h> void reverse(char *s, int j , int k ); void swap(char *, char *); int main(void) { char phrase[] = "by the sea, by the beautiful sea"; reverse(phrase, 3, 17); printf("%s\n", phrase); return 0; } void reverse(char *s, int j, int k ){ if(j < k) { swap(&s[j], &s[k]); reverse(s, ++j, --k); void swap(char *p, char *q) { char tmp; tmp = *p; *p = *q; *q = tmp; reverse[3] ~ reverse[17]에 있는 문자들을 3-17, 4-16, 5-15, 6-14, …번째의 문자들을 각각 swap하는 부분이다. by eht yb, aes eht beautiful sea

Quick Sort Quick Sort의 Sorting process 12 3 6 18 7 15 10 low high 3 6 low는 첫 번째 element, high는 마지막 element로 지정 12 3 6 18 7 15 10 low high high와 low를 비교해서 큰수를 buffer에 저장한 후 low에 10을 저장하고 low + 1 . 3 6 18 7 15 10 12 low high 3과 12를 비교해서 12가 3보다 크므로 low + 1 . 10 3 6 18 7 15 12 low high

Quick Sort Quick Sort의 Sorting process 10 3 6 18 7 15 12 low high 10 3 6과 12를 비교해서 12가 6보다 크므로 low + 1 . 10 3 6 18 7 15 12 low high low가 18이고 high가 12이므로 18이 12보다 크므로 18을 high에 넣고 high – 1 . 10 3 6 18 7 15 12 low high 15와 12의 값을 비교 10 3 6 7 15 18 12 low high

Quick Sort Quick Sort의 Sorting process 10 3 6 7 15 18 12 low high 10 3 15보다 12가 크므로 다시 high – 1 하여 7을 기억. 10 3 6 7 15 18 12 low high 12보다 7이 작으므로 7을 low의 element에 저장한 후 low + 1. 10 3 6 7 15 18 12 low, high low가 가리키는 값과 high가 가리키는 값이 같으면 buffer에 있던 12를 저장하고 해당 process 종료. 10 3 6 7 12 15 18 low middle 10 3 6 7 12 15 18 next process middle를 중심으로 왼쪽은 작은 값 오른쪽은 큰값.

Quick Sort Quick Sort code #include <stdio.h> #define N 10 void quicksort(int a[], int low, int high); int split (int a[], int low, int high ); void main(void) { int a[N], i; printf("Enter %d numbers to be sorted: ", N); for ( i = 0; i < N; i++ ) scanf("%d", &a[i]); quicksort(a, 0, N - 1); printf("In sorted order: "); for( i = 0; i < N; i++ ) printf("%d ", a[i]); printf("\n"); return 0; }

Quick Sort Quick Sort 예제 void quicksort( int a[], int low, int high ) { int middle; if (low >= high) return; middle = split(a, low, high); quicksort(a, low, middle - 1); quicksort(a, middle + 1, high ); } low와 high가 가리키는 기억장소의 위치가 서로 만나는 곳을middle로 한다. middle보다 작은 왼쪽구간 에 대해서 quicksort를 같은 과정으로 실행 middle보다 큰 오른쪽구간 에 대해서 quicksort실행 quicksort는 recursive function이다.

Quick Sort int split( int a[], int low, int high ) { int part_element = a[low]; for( ; ; ) while ( low < high && part_element <= a[high] ) high--; if (low >= high) break; a[low++] = a[high]; while(low < high && a[low] <= part_element) low++; if(low >= high ) a[high--] = a[low]; } a[high] = part_element; return high; low와 high가 가리키는 기억장소 의 위치를 각각 증가, 감소 시키는 함수부분. Enter 10 numbers to be sorted: 9 16 47 82 4 66 12 3 25 51 ꎠ In sorted order: 3 4 9 12 16 25 47 51 66 82

수고하셨습니다 Recursion