Internet Computing Laboratory @ KUT Youn-Hee Han 4장. 재귀호출 Internet Computing Laboratory @ KUT Youn-Hee Han

1. 상징적 의미 도미노 100번째 것이 반드시 쓰러진다는 사실을 증명하라 재귀적 알고리즘(Recursive Algorithm) 99번째 것이 쓰러지면 인접한 100번째 것이 쓰러지니, 99번째 것이 반드시 쓰러진다는 사실을 증명하라 98번째 것이 쓰러지면 인접한 99번째 것이 쓰러지니, 98번째 것이 반드시 쓰러진다는 사실을 증명하라 … 처음 것이 반드시 쓰러진다는 사실을 증명하라 그건 직접 밀었기 때문에 반드시 쓰러진다. Data Structure

1. 상징적 의미 Divide and Conquer (분할정복) Recursive Call (재귀호출) 큰 문제를 작은 문제로 바꿈 작은 문제 역시 큰 문제와 동일하다 문제의 크기만 다르다 Recursive Call (재귀호출) Self Call 큰 문제를 분할 정복하여 풀다 보니 작은 문제를 풀 필요성이 생기고, 그 작은 문제 역시 원래 문제와 같은 스타일이기 때문에 재귀 호출이 필요하게 됨 Base Case (베이스 케이스, 아주 작은 문제) 직접 해결할 정도로 작아짐 Degenerate Case Data Structure

1. 상징적 의미 A recursive call is a function call in which the called function is the same as the one making the call. In other words, recursion occurs when a function calls itself! We must avoid making an infinite sequence of function calls (infinite recursion). Each recursive algorithm must have at least one basecase if (some condition for which answer is known) // base case solution statement else // general case recursive function call Data Structure

2. 이진 탐색 Sequential Search (=Linear Search) Binary Search 한 번에 문제의 크기가 반으로 줄어듦 문제 크기 감소: N, N/2, N/4, …., 1 Infinite Loop 에 빠지지 않도록 조심 재귀호출은 반드시 베이스 케이스에 도달해야 함 [Pseudo-code] BinarySearch(SearchRange)  {           괄호 안은 탐색범위 if (One Page)                           베이스 케이스     Scan Until Found; else {   Unfold the Middle Page;            가운데 펼침     Determine Which Half;              전반부, 후반부 판단    if First Half BinarySearch(First Half);      전반부 재귀호출    else BinarySearch(Second Half);   후반부 재귀호출 } Data Structure

3. 재귀적 팩토리얼 From mathematics, we know that 20 = 1 and 25 = 2 * 24 In general, x0 = 1 and xn = x * xn-1 for integer x, and integer n > 0. Here we are defining xn recursively, in terms of xn-1 Data Structure

3. 재귀적 팩토리얼 n! = n * (n-1) * (n-2) * ... * 1 (단, 1! = 0! = 1) Data Structure

3. 재귀적 팩토리얼 Data Structure

3. 재귀적 팩토리얼 n! = n • (n-1) • (n-2) • ... • 1 (단, 1! = 0! = 1) [소스코드] int Factorial(int n) { if (n = = 1) return 1; else                return(n * Factorial(n-1)); }    Stack Expands  Parm. n = 4 Ret. Val = ?  Parm. n = 3 Parm. n = 2 Parm. n = 1    Ret. Val = 4 * 6  Ret. Val = 3 * 2 Ret. Val = 2 * 1 Ret. Val = 1                                            Stack Shrinks  Data Structure

Three-Question Method of verifying recursive functions 3. 재귀적 팩토리얼 Three-Question Method of verifying recursive functions Base-Case Question: Is there a nonrecursive way out of the function? Smaller-Caller Question: Does each recursive function call involve a smaller case of the original problem leading to the base case? General-Case Question: Assuming each recursive call works correctly, does the whole function work correctly?

4. 문자열 뒤집기 문제 정의 재귀적 접근방법 길이 4인 문자열 “Good”가 주어지면 결과로서 “dooG”를 얻음 길이 n의 문제를 길이 n-1의 문제로 환원 주어진 문자열의 길이를 하나 줄이기 위하여 하나의 문자를 떼어냄 어떤 문자를 떼어내는가? void Reverse(char S[ ], int Size) { if (Size = = 0) return;                        //  호출함수로 되돌아감 else {   printf("%c", S[Size-1]);       // 마지막 문자를 쓰기 Reverse(S, Size-1);            // 재귀호출 } 재귀호출에서 되돌아가는 과정에서는 아무런 작업을 하지 않음 Data Structure

4. 문자열 뒤집기 void Reverse(char S[ ], int First, int Last) { if (First > Last) return;          else { printf("%c", S[First]);  Reverse(S, First+1, Last); } 호출방법: Reverse(“Good”, 0, 3); void Reverse(char S[ ], int First, int Last) { if (First > Last) return;          else { Reverse(S, First+1, Last); printf("%c", S[First]);  } Data Structure

4. 문자열 뒤집기 void Reverse(char S[ ], int First, int Last) { if (First > Last) return;          else { Reverse(S, First+1, Last); printf("%c", S[First]);  } First = 0 Last = 3 Reverse(S, 1, 3) First = 1 Reverse(S, 2, 3)  First = 2 Reverse(S, 3, 3) First = 3 Reverse(S, 4, 3) First = 4    printf(S[0]) printf(S[1])  printf(S[2]) printf(S[3]) Fast = 3 return Data Structure

5. K번째 작은 수 찾기 문제 정의 Partition (파티션) Pivot (피벗) 예: 10, 7, 2, 8, 3, 1, 9, 6 이라는 숫자 중에서 세 번째 작은 수는 3 정렬하는 것이 허용되지 않는다. Partition (파티션) 어떤 수를 중심으로 주어진 수들을 두 그룹으로 나누는 작업 기준이 되는 수를 중심으로 그보다 작은 것들은 왼쪽 기준이 되는 수를 중심으로 그보다 큰 것들은 오른쪽 Pivot (피벗) 파티션을 위하여 기준이 되는 수 Data Structure

5. K번째 작은 수 찾기 임의로 Pivot 설정 Down Pointer와 Up Pointer설정 Down은 피벗보다 작거나 같은 것, Up은 피벗보다 크거나 같은 것 찾음   10 7 2 8 3 1 9 6 Up Down •   10 7 2 8 3 1 9 6 •   10 7 2 8 3 1 9 6 Data Structure

5. K번째 작은 수 찾기 Swapping 두 Pointer가 일치하거나 교차할 때까지 3),4)를 반복 •   1 7 2 8 3 10 9 6 Swapping 두 Pointer가 일치하거나 교차할 때까지 3),4)를 반복 Up Pointer 위치에 있는 숫자와 피벗을 스와핑   • 1 7 2 8 3 10 9 6   • 1 3 2 8 7 10 9 6   • 1 3 2 8 7 10 9 6   • 1 3 2 8 7 10 9 6   p 1 3 2 6 7 10 9 8 Data Structure

5. K번째 작은 수 찾기 파티션 세 번째 작은 수 찾기 피벗보다 작은 것은 왼쪽으로, 피벗보다 큰 것은 오른쪽으로 전체 데이터가 정렬된 상태는 아님 모든 데이터가 정렬되어도 피벗 위치는 불변! K가 4라면 네 번째 작은 수를 이미 찾은 것임 세 번째 작은 수 찾기 분할된 왼쪽에 대해서 다시 파티션을 가함 (결과 p = 2) 분할된 오른쪽에 대해서 다시 파티션을 가함: self-swap (결과 p = 3)   p  1 3 2 6 7 10 9 8 • 1 3 2   p 1 2 3 p 3 Data Structure

6. Fibonacci Sequence F(n) = F(n-1) + F(n-2) (단, F(0) = 0, F(1) = 1) Recurrence Relation 재귀 호출 하나가 다른 여러 재귀호출의 조합 형태로 나타남 int Fibonacci(int n) { if (n < 2) return 1;      //베이스 케이스 F(0) = F(1) = 1 else return (Fibonacci(n-1) + Fibonacci(n-2)); // 재귀호출 } Data Structure

7. 재귀 함수의 작성 Step 1 Step 2 Step 3 Step 4 더 작은 문제로 표시할 수 있는지 시도 문제 크기를 하나씩 줄이는 방법 반으로 줄이는 방법 다른 여러 개의 작은 문제의 조합으로 표시하는 방법 문제 크기 파라미터 N을 확인 Step 2 문제를 직접 풀 수 있는 것이 어떤 경우인지 베이스 케이스 확인 Step 3 N이 줄어서 반드시 베이스 케이스를 만나는지 확인 N이 양수인지 음수인지,  짝수인지 홀수인지, 또는 부동소수인지 정수인지 모든 경우에 대해 모두 검증. Step 4 베이스 케이스와 베이스 케이스가 아닌 경우를 나누어서 코드를 작성 Data Structure

8. 재귀 호출의 효율성 재귀 호출시 Activation Record의 비효율 공간적 비효율(저장 공간) 시간적 비효율(저장, 복원에 걸리는 시간) 가능하다면 반복문으로 대치하는 것이 유리 int Factorial(int n) {                       int product = 1;   for (int i = 1; i <= n; i++) product *= i; return product; }        void Reverse(char S[ ], int Size)  { while (Size > 0) { printf("%c", S[Size-1]);             --Size;                             } }     Data Structure

8. 재귀 호출의 효율성 시간적, 공간적 부담을 배제할 수 있음 int Fibonacci(int n) { int F[Max]; F[0] = 1; F[1] = 1; for (int i = 2; i <= n; i++) F[i] = F[i-2] + F[i-1]; return (F[i]); } Data Structure

9. Tail Recursion 재귀호출 명령이 함수 마지막에 위치 꼬리 재귀를 사용한 팩토리얼 되돌아올 때 할 일이 없는 재귀호출 새로운 활성화 레코드 공간을 만들지 않고 이전 공간 재사용 대부분의 컴파일러가 지능적으로 이를 처리함 꼬리 재귀를 사용한 팩토리얼 int Factorial(int n, int a) { if (n = = 0) return a;               // a에 결과 값이 축적됨 else return Factorial(n-1, n*a);  // 꼬리 재귀 } Data Structure

9. Tail Recursion return (N * Factorial(N-1)) - Animation 주의: Factorial(N-1) 결과가 리턴 되면 거기에 N을 곱하는 일이 남아 있음. return (N * Factorial(N-1)) - Animation Data Structure