[Algorithm] 재귀적 함수(순열,조합,하노이탑)

재귀 함수는 자신을 다시 호출하는 함수다. 반복문과 같이 일정한 조건을 충족할때까지 계속 자기 자신을 반복하는 함수다.

대표적으로 피보나치 수열이 있다.
ex) 1, 1, 2, 3, 5, 8, ...
a(n) = a(n-1) + a(n-2)를 계산하는 것이다.

이때 n값이 주어졌을 때 결과값을 return하는 함수를 만들어 보겠다.

public int fibo(int n){
       if(n == 1 || n == 2){
           return 1;
       }
       return fibo(n-1) + fibo(n-2);
   }

수열을 만드는 식을 그대로 활용하면 피보나치 수열에 대한 재귀함수를 만들 수 있다. 위 함수의 단점으로는 효율성이 떨어진다. 한번 계산한 내용도 반복해서 계산하기 때문이다. 이를 해결하기 위해서는 동적계산법으로 해결할 수 있다. 한번 계산한 내용을 저장해두고 다시 계산해야되는 경우 결과값만 꺼내서 사용하는 것인데 추후 다루도록 하겠다.

외부에 static으로 변수를 추가해도 원하는 계산을 할때 유용하다.

이 글을 쓰면서 본격적으로 다루고 싶었던 내용은 순열과 조합이다. 고등학생때 nCr, nPr 하면서 원리와 공식을 알고 사용하던 것들이라 우습게 생각했다. 하지만 어떤 조합이 나오는지 하나씩 만들어서 뽑아내는 걸 만드려니 어려웠는데 재귀로 해결하는 글을 읽었고 공부하게 되었다.

// 순열
public void permutation(List<String> arr, List<String> result, int n, int r) {
       if (r == 0) {
           System.out.println(result.toString());
           return;
       }

       for (int i = 0; i < n; i++) {
           result.add(arr.remove(i));
           perm2(arr, result, n - 1, r - 1);
           arr.add(i, result.remove(result.size() - 1));
       }
   }

재귀 함수를 반복문안에서 쓰게 되니 디버깅하면서 상당히 헷갈렸다. 이곳저곳 통통 튀어다니는 느낌이라 몇번째 재귀인지 파악하면서 이해하려고 노력했다.

// 조합
public void combination(List<String> arr, List<String> result, int index, int n, int r) {

       if (r == 0) {
           System.out.println(result.toString());
           return;
       }

       for (int i = index; i < n; i++) {

           result.add(arr.get(i));
           combination(arr, result, i + 1, n, r - 1);
           result.remove(result.size() - 1);
       }
   }

마지막으로 재귀함수에 대해서 조금 더 이해할 겸 하노이의 탑 문제를 공부해봤다.

하노이의 탑 문제는 3개의 봉을 이용해서 n개의 원판을 이동하는 것이다. 이때 몇가지 규칙이 있는데 규칙은 아래와 같다.
1. 한번에 원판 한개만 이동할 수 있다.
2. 원판마다 크기가 다르다.
3. 모든 원판은 크기가 큰 순서대로 밑에서부터 쌓여있다.
4. 큰 원판 아래 작은 원판이 올수 없다.
5. 모든 원판을 같은 순서대로 다른 봉으로 옮겨야 한다.

-> 이때 옮겨야 되는 횟수와 원판이 어디서 어디로 옮겨가는지 파악하는 문제다.

이 문제의 점화식은 a(n) = 2 * a(n-1) + 1이다. 조금 상세하게 설명하면 a(n)은 a(n-1)개를 다른 봉으로 이동하면 1개의 원판이 남는다. 이 원판을 목적지로 이동하고 a(n-1)개를 다시 목적지로 이동하면 a(n)이 완성된다.

이 내용을 재귀함수로 만들면 아래와 같다. 이때 횟수는 count를 이용해서 파악할 수 있다.

// n개의 원판을 start, mid, to 3개의 봉을 이용해서 옮긴다.
public static int count = 0;
public static void Hanoi(int n, int start, int mid, int to) {
	count++;
       // 가장 위에있는 원판만 움직일 수 있다
       if (n == 1) {
           System.out.println(start + " " + to);
           return;
       }

       // #1 n-1개를 중간으로 이동
       Hanoi(n - 1, start, to, mid);

       // #2 : 가장 아래있는 원판을 목적지로 이동
       System.out.println(start + " " + to);

       // #3 중간에 이동된 n-1개의 원판을 목적지로 이동
       Hanoi(n - 1, mid, start, to);

   }

재귀함수에 대해서 활용하면서 조금더 자세하게 알아봐야 겠다. 깊이우선탐색에서도 쓰이니 다른 알고리즘을 공부하면서 더욱 확고하게 알아둬야겠다.

reference
-https://codevang.tistory.com/297 (순열과 조합)
-https://st-lab.tistory.com/96 (하노이 탑)