[자료구조 알고리즘] 재귀 호출 : 논리를 코딩하기

[재귀함수 호출]

- S(n) 결과값 도출을 위해 S(n-1)이 필요할 때 재귀 호출을 사용

=> 패턴화를 위해 예시 경우의수 2~3가지를 대입해서 실행해보고 패턴화해서 코드로 짜기

void Recursive(int num) {
     if(num <= 0) {
          return ;
     }
     printf("Recursive call %d\n", num);
     Recursive(num-1);
}
 
int main(){
     Recursive(3);
     return 0;
}

- 재귀 호출 가능하도록 만들어짐 : 함수 내에서 함수를 호출하는 것

- 명령문 원본 -> 복사본(Recursive) -> 복사본(Recursive) -> 복사본(Recursive)

=> 원본의 복사본 실행

=> 명령문 실행 : 명령문은 CPU로 이동(복사)되어 실행

=> 메모리(스택)에 이전 함수(복사본)의 주소가 저장 : 마지막 호출된 복사본이 종료되면 이전 함수(복사본)으로 돌아감

- 재귀 함수 탈출 조건 : 끝남 조건, 무한루프 X

=> OutOfMemory 

- 반복문을 간결하게 작성함 : 함수를 스택에 쌓고 연산하는 것보다 반복문을 사용하는 것이 빠를 수 있겠지만 코드를 간결하게 만들 수 있음

=> 결과값을 차곡차곡 

[재귀 호출 활용]

(1) n! : 팩토리얼, 순열구하기

int Factorial(n){
     if(n == 0){
          return 1;
     } else {
          return n * Fatorial(n-1);
     }
}
 
int main(){
     printf("%d\n", Fatorial(5));
 
     return 0;
}
 

- 리턴값에 리턴값을 리턴값에 리턴값을

(2) 피보나치 수열 

- 토끼 번식 관련 수열 : 0 -> 1쌍 -> 2쌍 -> 3쌍 -> 5쌍 -> 8쌍 - - - 

=> 1쌍이 1쌍만 놓음

- 자연 속에서 발견된 수열 : 여러 곳

- 피보나치 수열의 뒷수/앞수 : 1.618xxxx 로 수렴(황금비)

int Fibo(n){
     if(n==1){
          return 0;
     } else if(n==2){
          return 1;
     } else {
          return Fibo(n-2) + Fibo(n-1);
     }
}
 
int main(){
     int i;
     for(i=1; i<10; i++){
          printf("%d ", Fibo(i));
     } // 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
 
     Fibo(7); // 함수 호출 순서, 관계(어떤 함수들이 호출되는가) 한번 쫓아가보기
 
     return 0;
}
 

- 알고리즘 : 문제에 대한 논리를 먼저 세우고, 코드화

- 스택에 이전 호출 함수 저장 : 돌아감(+= 리턴값)

- 함수 : 호출 관계 + 순서 한번쯤 쫓아가보기

(3) 하노이타워 : n개의 블럭(크기 순서대로 꽂혀있음)을 A 타워에서 C 타워로 그대로 옮기기

- 패턴화를 위해 1개, 2개, 3개 블럭 일 때 어떻게 진행되는지 직접 그려서 해보기 : 함수 호출 관계 따라가보기

=> 1개 일 때 : 바로 C로 옮김

=> 2개 일 때 : 첫번째 것을 B로 옮긴 후 마지막번 째 것을 C로 옮김, 그리고 B에 꽂힌 것을 C로 옮기면 끝

=> 3개 일 때 : 첫번째 것을 C로 옮긴 후 두번째 것을 B, 다시 C에 있는 것을 B, 마지막번 째 것을 C로, B에 있는 것을 차례대로 A를 이용해 C로 옮김

=> n개 일 때 : 마지막 번 째 것은 C로 옮기는 것 밖에 하지않음, 나머지 위의 블럭들은 n-1일 때 상황을 반복함

=> 수식화 : S(n) = S(n-1) + 1

- 수식을 코드로 변환

void Hanoi(int n, char begin, char mid, char end) {
    if(n==1){
        printf(“원반%d가 %c 로 옮겨짐”, n, end);
        return ;
    }
 
    Hanoi(n-1, begin, end, mid);
    printf(“%d 가 %c 로 옮겨짐”, n, end);
    Hanoi(n-1, mid, begin, end);
}
 

=> 4개의 링일 때 나머지 3개를 다른 곳으로 옮기고, 마지막 1개를 C로 옮김(출력)

    => 3개의 링일 때 나머지 2개를 다른 곳으로 옮기고, 마지막 1개를 C로 옮김(출력)

        => 2개의 링일 때 나머지 1개를 다른 곳으로 옮기고, 마지막 1개를 C로 옮김(출력)

            => 1개의 링일 때 C로 옮김(출력)

            => 함수 관계 파생 : 함수 호출 관계 파악하기가 중요함

=> 재귀적으로 호출 : S(n)의 결과를 얻기위해 S(n-1) ——— 을  호출함