Activation Records & Recursion Internet Computing Laboratory @ KUT Youn-Hee Han

프로세스 이미지와 변수의 영역 프로세스 이미지 C 프로그램과 이미지의 내용 프로세스는 일정한 메모리를 배정 받아 사용 프로그램 실행에 필요한 어셈블러 코드, 변수가 저장 원칙적으로 한 프로세스는 다른 프로세스의 메모리 영역에 접근 불가 C 프로그램과 이미지의 내용 #include <stdio.h> #include <stdlib.h> extern char **environ; //extern 변수 int init_global_var = 3; //초기화된 global 변수 int uninit_global_var; //초기화되지 않은 global 변수 static int global_static_var; //static global 변수 int main(int argc, char **argv) { int auto_var; //automatic 변수 (local variable) static int local_static_var; //local_static 변수 register int reg_var; //register 변수 char *auto_ptr; //automatic 변수 (local variable) auto_ptr = (char *)malloc(10); return 0; }

프로세스 이미지와 변수의 영역 프로세스의 메모리 영역과 저장되는 변수 종류 메모리 영역 변수 환경변수 영역 environ 코드 영역 어셈블된 프로그램 코드 정적 데이터 영역 초기화된 영역 init_global_var = 3 초기화 안된 영역 (0으로 할당) uninit_global_var, global_static_var, local_static_var 힙 malloc()이 할당한 10바이트 스택 argc, argv, auto_var, reg_var (레지스터), auto_ptr

프로세스 이미지와 변수의 영역 auto register static global 내부 static 외부 static 기억장소 stack memory static data memory 초기화 횟수 실행시 매번 1회 초기화하지 않을 경우 쓰레기값 0 or NULL 선언된 block (or function)에서 실행후 값의 존재 유무 X O 선언된 block (or function) 이외에서의 접근 같은 Source File의 다른 함수에서 참조 다른 Source File에서 참조

프로세스 이미지와 변수의 영역 다음 코딩예의 출력 결과는? #include <stdio.h> void test(void) { static int s_count=0; int a_count=0; s_count++; a_count++; printf("static count=%d\tauto count=%d\n", s_count, a_count); } void main(void) { int i; for(i=0; i<5; i++) test();

활성화 레코드 활성화 레코드 (Activation Record) Activation Record is a chunk of computer memory which holds the arguments and local variables of the function. Activation Record corresponds to a call to a function which has not yet terminated with a return. 즉, 각 함수의 호출은 그 함수가 사용하는 모든 변수들을 위한 기억장소를 포함하는 활성화 레코드(activation record)를 생성한다.

활성화 레코드 main함수 호출에 따른 활성화 레코드 int a; 전역 변수 void main( ) { int b; char *s;       지역변수(스택) s = malloc(10);      10 바이트짜리 동적변수(힙) b = fcn(5); free (s); } 전역변수 a 기계코드 main( ) 힙 *s 미사용 공간   스택 (main 함수의 활성화 레코드) Local Variables b, s Homeward (귀환) Address 204번지 Value Parameters Return Value

활성화 레코드 main 함수에서 일반 함수 호출에 따른 활성화 레코드 int a; void main( ) { int b; char *s;   s = malloc(10); b = fcn(5); free (s); } int fcn(int p)  {   int b = 2;     b = b + p; return (b); 전역변수 a 기계코드 main( ) fcn1( ) 힙 *s 미사용 공간   스택 (fcn 함수의 활성화 레코드) Local Variables b Homeward (귀환) Address 230번지 Value Parameters p: 5 Return Value 7 (main 함수의 활성화 레코드) b, s Homeward Address 204번지

활성화 레코드 Context Switching Stack Overflow Heap Overflow? 새로운 활성화 레코드 생성 연속적인 함수호출에 따라 활성화 레코드 스택이 생성 함수 종료시 제일 위의 활성화 레코드가 사라짐으로써 직전의 상황을 복원 Stack Overflow 무한 루프내에서 재귀적 함수 호출을 계속할 때 Heap Overflow? 무한 루프내에서 동적 메모리 할당을 계속 할 때 더 이상 할당할 힙 공간이 없을 때 NULL 을 반환 힙 메모리 소진을 대비한 코드 nodePtr = (NODE*)malloc(sizeof(NODE)); if (nodePtr == NULL) …..

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

재귀 호출 Approach to repetitive algorithms Iteration (loop) while 루프, for 루프 Recursion (function call to itself) 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! Suitable for problem breaking-down Divide-and-conquer Many algorithms are drastically simplified by recursion

Factorial – A Case Study Iterative definition of factorial Recursive definition of factorial Recursive Definition A의 정의 파트에 다시 A를 사용하는 정의

Factorial – A Case Study Factorial of 3 (by recursion) Factorial(3) = 3 * factorial(2) = 3 * 2 * factorial(1) = 3 * 2 * 1 * factorial(0) = 3 * 2 * 1 * 1 = 6

Factorial – A Case Study Iterative Algorithm of Factorial

Factorial – A Case Study Recursive Algorithm of Factorial

Factorial – A Case Study Trace of Recursion [소스코드] int recursiveFactorial(int n) { if (n = = 1) return 1; else                return(n * recursiveFactorial(n-1)); }

Factorial – A Case Study Function call is implemented using a special type of memory, called “Activation Record” Ex) recursiveFactorial(1) calls recursiveFactorial(0) void recursiveFactorial(1) { … recursiveFactorial(0); } void recursiveFactorial(0) { … } locals of recurFac(0) Activation Record for recursiveFactorial(0) parameter of recurFac(0) locals of recurFac(1) Activation Record for recursiveFactorial(1) parameter of recurFac(1) Activation Record for recursiveFactorial(2) Activation Record for recursiveFactorial(3)

Factorial – A Case Study Activation Records for Recursive Call [소스코드] int Factorial(int n) { if (n = = 1) return 1; else                return(n * Factorial(n-1)); }    Activation Records (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                                           Activation Records (Stack) Shrinks 

Designing Recursive Algorithm Every recursive algorithm has two elements Solve a primitive problem  non-recursive solution Base case Reduce the size of problem  recursion General case

Designing Recursive Algorithm Rules for designing a recursive algorithm 1. Determine base case Non-recursive solution of primitive case such as n = 0, 1 2. Determine general case Break down the problem into sub-problems which are the same, but smaller than original Assume sub-problems are already solved Ex) To calculate factorial(n), assume factorial(n-1), factorial(n-2), …, factorial(0) are solved 3. Combine base and general cases

Designing Recursive Algorithm Recursion is effective for Problems that are naturally recursive Binary search Algorithms that use a data structure naturally recursive Tree Disadvantage of recursion Function call overhead Time Stack memory

Designing Recursive Algorithm Step 1 더 작은 문제로 표시할 수 있는지 시도 문제 크기를 하나씩 줄이는 방법 반으로 줄이는 방법 다른 여러 개의 작은 문제의 조합으로 표시하는 방법 문제 크기 파라미터 N을 확인 Step 2 문제를 직접 풀 수 있는 것이 어떤 경우인지 베이스 케이스 확인 Step 3 N이 줄어서 반드시 베이스 케이스를 만나는지 확인 N이 양수인지 음수인지,  짝수인지 홀수인지, 또는 부동소수인지 정수인지 모든 경우에 대해 모두 검증. Step 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);            // 재귀호출 } 재귀호출에서 되돌아가는 과정에서는 아무런 작업을 하지 않음

문자열 뒤집기 문자열 뒤집기 A B A와 B중 어느 것이 맞을까? 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); B void Reverse(char S[ ], int First, int Last) { if (First > Last) return;          else { Reverse(S, First+1, Last); printf("%c", S[First]);  } A와 B중 어느 것이 맞을까?

문자열 뒤집기 문자열 뒤집기 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

최대공약수 찾기 Greatest Common Divisor (최대공약수) GCD’s Recursive Definition (Euclidian Algorithm) Recursive algorithm gcd(a, b) = a if b = 0 = b if a = 0 = gcd(b, a % b) otherwise int gcd (int a, int b) { if (b == 0) // Base Case return a; if (a == 0) // Base Case return b; return gcd (b, a % b); // General Case }

피보나치 수열 Fibonacci Numbers Each number is the sum of previous two numbers 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … Recursive Definition Recursive Algorithm Fibonacci(n) = 0 if n = 0 = 1 if n = 1 = Fibonacci(n-1) + Fibonacci(n-2) long fib (long num) { // Base Case if (num == 0 || num == 1) return num; // General Case return (fib (num - 1) + fib (num - 2)); }

피보나치 수열 Fibonacci Numbers

피보나치 수열 Fibonacci Numbers # of function calls to calculate Fibonacci numbers

재귀 호출의 효율성 재귀 호출시 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;                             } }    

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

하노이탑 Towers of Hanoi Input Problem Rules Three towers (source, destination, auxiliary) n disks of different diameters placed on source tower in decreasing diameter Problem Move all disks from source tower to destination tower Rules Only one disk can be moved at any time No disk can be placed on top of a disk with a smaller diameter

하노이탑 Towers of Hanoi Algorithm design Base case: only one disk to move Just move it General case: # of disk > 1  How to break down the problem ?

하노이탑 Towers of Hanoi Moving 2 disks (from source to destination) 1. Move one disk from source to auxiliary 2. Move one disk from source to destination 3. Move one disk from auxiliary to destination

하노이탑 Towers of Hanoi Moving 3 disks (from source to destination) 1 2 3 1. Move two disk from source to auxiliary 2. Move one disk from source to destination 3. Move two disk from auxiliary to destination 1 2 3

하노이탑 Towers of Hanoi Moving n disks (from source to destination) 1. move n -1 disks from source to auxiliary 2. move 1 disk from source to destination 3. move n -1 disks from auxiliary to destination char *source="A 막대"; char *destination="C 막대"; char *auxiliary="B 막대"; void Towers(int n, char*source, char*destination, char*auxiliary) { static int step = 0; if ( n > 0 ) { Towers(n-1,source, auxiliary, destination); printf("Step %d: %s에서 %s로.\n", ++step, source, destination); Towers(n-1,auxiliary, destination, source); }

하노이탑 Towers of Hanoi Moving 3 disks [Output] Towers(3,A,C,B) Towers(2,A,B,C) Towers(1,A,C,B) Step 1: A 막대에서 C 막대로. Step 2: A 막대에서 B 막대로. Towers(1,C,B,A) Step 3: C 막대에서 B 막대로. Step 4: A 막대에서 C 막대로. Towers(2,B,C,A) Towers(1,B,A,C) Step 5: B 막대에서 A 막대로. Step 6: B 막대에서 C 막대로. Towers(1,A,C,B) Step 7: A 막대에서 C 막대로.

하노이탑 Towers of Hanoi Moving 3 disks [Output] Towers(3,A,C,B) Towers(2,A,B,C) Towers(1,A,C,B) Step 1: A 막대에서 C 막대로. Step 2: A 막대에서 B 막대로. Towers(1,C,B,A) Step 3: C 막대에서 B 막대로. Step 4: A 막대에서 C 막대로. Towers(2,B,C,A) Towers(1,B,A,C) Step 5: B 막대에서 A 막대로. Step 6: B 막대에서 C 막대로. Towers(1,A,C,B) Step 7: A 막대에서 C 막대로.