제14장 자기호출과 함수포인터 자기호출 함수 (Recursive Functions) 재귀적 함수 recursion 제14장 자기호출과 함수포인터 자기호출 함수 (Recursive Functions) 재귀적 함수 recursion recursive call 재귀적인 문제의 특성 (1) 정지경우(stopping cases): 비 재귀적 해를 가짐 (2) 축소경우(reducible cases): 정지경우에 좀 더 근접한 문제들로 축소 가능한 경우 (3) 궁극적으로 문제는 정지경우들로 축소 가능 2018-09-16 제14장 자기호출과 함수포인터

재귀적인 문제의 예. 하노이의 탑 (Towers of Hanoi) 문제 - 3개의 탑 또는 말뚝(towers or pegs) A, B, C - 탑 A에는 모두 크기가 다른 n장의 디스크(disks) - 디스크 번호: 작은 것부터 차례로 1, 2, ..., n - 문제의 목표는 탑 A에 있는 n장의 디스크를 탑 C로 다음 규칙들을 지키며 (2n -1)회에 옮기는 순서를 말하는 것이다. 1. 한번에 오직 한개의 디스크만을 옮길수 있고, 이 디스크는 반드시 탑의 맨위에 있는 디스크이어야 한다. 2. 작은 디스크위에 큰 디스크를 올려 놓을 수 없다. 2018-09-16 제14장 자기호출과 함수포인터

재귀적인 문제의 예 (계속) n factorial의 계산 문제 수식을 폴랜드 표기법 (postfix form) 으로 변환문제 Quicksort Eight Queen 문제 등. 2018-09-16 제14장 자기호출과 함수포인터

문제의 분할 이전의 그림과 같이 다섯개의 디스크를 탑 A에서 C로 옮기는 경우를 생각해 보자. 이전의 그림과 같이 다섯개의 디스크를 탑 A에서 C로 옮기는 경우를 생각해 보자. 주어진 문제에서 정지경우와 축소경우는 ? 원래의 문제는 다음과 같은 세개의 문제로 분할 가능: 1. 탑 A에서 탑 B로 4개의 디스크를 옮겨라. 2. 5번 디스크를 탑 A에서 탑 C로 옮겨라. 3. 탑 B에서 탑 C로 4개의 디스크를 옮겨라. 오직 한 개의 디스크를 옮기는 경우이다(예를 들면 2번 디스크를 탑 A에서 C로 옮겨야 하는 경우). 주어진 문제보다 좀 더 간단한 문제는 위와 같은 조건하에서 4개의 디스크를 옮기는 것이며 또 좀 더 간단한 문제는 3개의 디스크 문제 등과 같이 된다. 따라서 원래의 디스크 5개 문제를 한 개 이상의 좀 더 작은 갯수의 디스크 문제로 나눌려고 한다. 2018-09-16 제14장 자기호출과 함수포인터

함수 Hanoi (A, B, C, n) main( ) { void Hanoi ( ); Hanoi ('P', 'Q', 'R', 3); /* L0 */ } void Hanoi (A, B, C, n) char A, B, C; { if (n >= 1) { Hanoi (A, C, B, n-1); /* L1 */ printf ("Move %d from %c to %c.\n", n, A, C); Hanoi (B, A, C, n-1); /* L2 */ } 2018-09-16 제14장 자기호출과 함수포인터

Hanoi(‘P’, ‘Q’, ‘R’, 3)의 추적 (tracing) 2018-09-16 제14장 자기호출과 함수포인터

자기호출과 실행시간스택 2018-09-16 제14장 자기호출과 함수포인터

14.3 자기호출 함수와 반복문 자기호출함수(재귀적함수) 사용 : 알고리즘을 간결하게 표현 함수호출/복귀오버헤드 14.3 자기호출 함수와 반복문 자기호출함수(재귀적함수) 사용 : 알고리즘을 간결하게 표현 함수호출/복귀오버헤드 반복문 이용 : 실행시간 단축. 교재477쪽에서 함수 power(a, b)를 2가지 방법으로 구현 2018-09-16 제14장 자기호출과 함수포인터

실행시간 스택과 사용자 정의 스택 14.4.2 변수의 기억장소 할당 14.4.3 사용자 정의 스택 교재488쪽 보조그림 설명 배열 stack을 push, pop을 경유하지 않고 외부에서 직접 사용한다면? 2018-09-16 제14장 자기호출과 함수포인터

14.5 자기참조 구조 self_referential structure: struct tnode { . . . 14.5 자기참조 구조 self_referential structure: struct tnode { . . . struct tnode *tnodep; }; struct tnode lee, kim; lee.tnodep = &kim; kim.tnodep = &lee; 그림으로 표현하면? 2018-09-16 제14장 자기호출과 함수포인터

이진 트리(binary trees) struct tnode{ char *word; int count; struct tnode *left; struct tnode *right; }; struct tnode *root 이진탐색트리 (binary search trees) 2018-09-16 제14장 자기호출과 함수포인터

단어정렬 예제 프로그램 (14-493.cpp) main( ): 전체적인 제어 getw( ): 단어입력 addt( ): 2진 트리에 단어를 삽입 tprint( ): 단어들을 출력 495쪽 getw( ) 에서 buf[bufp]부터 buf[0]까지의 문자들을 w(단어포인터)에 저장 2018-09-16 제14장 자기호출과 함수포인터

14.6 함수포인터 int (*fp)( ); 에서 fp는 int형을 반환하는 함수를 가리키는 포인터 int greater(a, b) int a, b; { . . . } 일때 fp = greater; (또는 fp = &greater( );) 와 같이 설정후에 (*fp)(x, y); 라고 쓰면 greater(x, y); 와 동일한 함수 호출 가능. 2018-09-16 제14장 자기호출과 함수포인터

포괄함수 또는 함수틀 generic function function template 예. 교재500쪽의 함수 sort( ) void sort (int a[ ], int n, int (*fp)(int, int)) 위에서 fp는 배열원소 비교를 위한 함수 포인터 교재506쪽의 void qqsort(void *v[ ], int left, int right, int (*comp)(void *, void *)) 위에서 ‘void *’는 어느 자료형에 대한 포인터가 와도 좋다는 뜻. 2018-09-16 제14장 자기호출과 함수포인터

Quicksort by C.A.R. Hoare 14_510.cpp n개의 데이터 정렬: Quicksort는 nlog2n 회의 대소비교 Bubble sort는 (1/2)n2회의 대소비교 2018-09-16 제14장 자기호출과 함수포인터