제14장 자기호출과 함수포인터 자기호출 함수 (Recursive Functions) 재귀적 함수 recursion

Presentation on theme: "제14장 자기호출과 함수포인터 자기호출 함수 (Recursive Functions) 재귀적 함수 recursion"— Presentation transcript:

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

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

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

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

5 함수 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 */ } 제14장 자기호출과 함수포인터

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

7 자기호출과 실행시간스택 제14장 자기호출과 함수포인터

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

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

10 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; 그림으로 표현하면? 제14장 자기호출과 함수포인터

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

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

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

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 *’는 어느 자료형에 대한 포인터가 와도 좋다는 뜻. 제14장 자기호출과 함수포인터

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