재귀 함수에 대한 고찰

자기 자신을 호출하는 함수인 재귀 함수를 코딩 문제를 풀다가 접하게 되었다.  
학부생 시절에 배웠던 기억이 난다.
바이너리 트리가 담고 있는 데이터들을 전부 출력 해주는 부분이었다.

이진트리 데이터들을 출력해주는 print_tree()라는 어떠한 함수를 만들었으면
root노드의 정보를 파라미터로 받아 root노드의 기점으로 왼쪽부터 이후, 오른쪽 노드들의 데이터를 출력해주는 구조로 기억한다.
위 사진대로라면 root 노드인 'A' 노드를 파라미터로 아래와 같이 함수를 호출한다.
print_tree('A');
이후, A노드를 기점으로 왼쪽 노드인 'B'노드를 파라미터로 또 해당함수를 아래와 같이 호출한다.
print_tree('B');
또 B노드를 기점으로 'D' 노드를 호출한다.  여기서 중요한것은 D노드는 자식 노드가 없다. 그렇다면 return.
이 return을 하는 행위가 재귀 함수의 탈출조건이 된다.
print_tree('D')로 처음 return을 하는 과정이 발생했다. 이후 B노드 입장에서 왼쪽 자식노드인 D노드의 펑션 콜을 정상 수행하여
return을 받았다면 오른쪽 자식노드를 훑어보는 로직을 가져가야 한다.
E노드를 호출하게 되어 H, I까지 모두 마쳤다면 상위 노드인 B노드 역시 return을 한다.
이런 앞선 과정대로 A노드의 오른쪽 자식 노드인 C노드를 수행.

이런 방식대로 간단하게 print_tree 함수를 표현해보자면 아래와 같을것이다.

struct NODE{
char NodeId='\0';
char left='\0';
char right='\0';
}

void print_tree(char root){
char NODE.NodeId = root;
printf("%c", NODE.NodeId);
if(NODE.NodeId->left='\0'){    //왼쪽 노드가 없다면 리턴
return;
}
print_tree(NODE.NodeId->left);  //왼쪽노드가 존재한다면 call
if(NODE.NodeId->right='\0'){ // 오른쪽 노드가 없다면 리턴
return;
}
print_tree(NODE>NodeId->right); // 오른쪽 노드가 존재한다면 call
}

정확한 코드는 아니지만 대충 이런식일것 같다.

또, 재귀 함수로 많이 나오는 예시중 하나는 하노이 탑이다.

사고력 창의력을 길러주는 하노이 탑 완구 제품인듯 하다.
하노이 탑의 룰은 3개의 폴중 왼쪽 or 오른쪽 가장자리에 위치해있는 피라미드 쌓기로 된 원판을 반대편 폴로 피라미드 형태로 이동 하면 된다.
다만, 원판이 이동중에 크기가 해당 원판보다 작은 원판 위에는 올라 갈수가 없다.

1
2
3
a     b    c  

위와 같이 a, b, c의 폴이 있다고 하면  a위에 있는 원판들을 c 폴에 옮기면 된다.  참고로 숫자는 원판의 크기를 의미한다.
그 이후 순서는 아래와 같다.

2
3           1
a     b    c  

3    2     1
a     b    c  


       1
3     2
a     b    c

       1
       2    3
a     b    c

            
1     2    3
a     b    c
        
             2
1           3
a     b    c

             1
             2
             3
a     b    c

원판이 3개 일 경우 7차례로 옮겨짐을 확인 할수 있다.  원판의 갯수에 따라 옮겨지는 횟수는 수학적으로 점화식을 통해 구할수 있다.

원판이 n+1개 있을때를 가정해보자.

n
n+1
a       b      c  

원판 n+1개를 c 폴로 옮기기 위한 토탈 횟수를 구하기 위해선 하노이 탑의 규칙대로 원판 n개를 b폴로 이동시킨 후에 n+1번째 원판을
c로 옮기고 b폴에 있던 n개의 원판들을 c폴로 옮겨주면 된다.

n+1    n
a       b      c  

         n    n+1
a       b      c  
                  n
                n+1
a       b      c  

결과적으로 n개의 원판이 b폴로 갔다 c폴로 이동했다.  n개의 원판이 한번 이동하는 횟수를 A라고 하면 2A
n+1번째의 원판이 a폴에서 c폴로 총 1번 이동했다.
따라서 n+1개의 원판을 하노이 탑쌓기를 하면 총 횟수는 2A+1 번이 된다.

하노이 탑 규칙대로 원판의 총 이동횟수는 구할수 있다 하자.....  
원판들이 폴에서 폴로 이동한 history를 출력하는것은 어떻게 처리를 할까?
예로, 원판 1개가 a폴에서 c 폴로 이동하였다면   "a to c"로 출력하는것이다.

결과적으론 재귀함수로 구현하면 해결할수 있는 문제이다.

hanoi라는 function을 구현했다고 가정하자.
먼저 hanoi라는 재귀 함수를 구현하기 앞서 무엇부터 고민 해봐야할까라는 의문이 떠올랐다.
하노의 탑의 규칙의 특징이 무엇인지를 잘 떠올려 보아야한다.

 

앞서 말한 규칙들이 잘 반영된 재귀함수이다. 

참고하길 바란다. 

 

        public static void Hanoi(int N, int start, int mid, int to) {
                // 이동할 원반의 수가 1개라면?
                if (N == 1) {
                        sb.append(start + " " + to + "\n");
                        return;
                }
                // STEP 1 : N-1개를 A에서 B로 이동
                Hanoi(N - 1, start, to, mid);

                // STEP 2 : 1개를 A에서 C로 이동
                sb.append(start + " " + to + "\n");

                // STEP 3 : N-1개를 B에서 C로 이동
                Hanoi(N - 1, mid, start, to);

        }
}

출처 : https://st-lab.tistory.com/96

 

 

[백준] 11729번 : 하노이 탑 이동 순서 - JAVA [자바]