재귀 알고리즘

• 재귀 알고리즘

 재귀란 어떤 사건이 자기 자신을 포함하고 있거나 또는 자기 자신을 사용하여 정의하고 있을 때 이를 재귀적(recursive)이라고 한다. 

 

• 재귀 알고리즘의 예시

    1. 팩토리얼 구하기

 팩토리얼은 본인을 포함해 본인보다 작은 자연수의 값을 다 곱한 값을 말한다. 그리고 0! = 1 로 정의 된다. 예를 들어 7!이 있으면 7! = 7 * 6 * 5 * 4 * 3 * 2 * 1 이되고 이는 7 * 6!과 같다.  이를 이용해 팩토리얼 구하는 알고리즘을 짜보자.

static int factorial(int n){
    if( n > 0) return n * factorial(n-1); // 재귀 호출
    else return 1; // n=0 이면 0!=1 return
}

 다음과 같이 재귀를 이용하면 간단하게 알고리즘이 완성된다. 그냥 정의 'n>0 이면 n! = n * (n-1)!이고 n=0이면 n!=1이다' 를 그대로 구현해 놓으면 된다. 이렇게 메서드 내에서 다시 자기 자신과 똑같은 메서드를 호출하는 방법을 재귀 호출(recursive call)이라 한다. 그리고 재귀의 방법에는 2가지가 있는데 factorial 메서드처럼 자신과 동일한 메서드를 호출하는 것을 직접 재귀라 하고, 메서드 a, b가 있을 때 a는 b를 호출하고 b는 a를 호출해 계속 반복되는 구조를 간접 재귀라고 한다.

 

 이렇게 팩토리얼 처럼 문제를 풀때 재귀로 정의되면 재귀 알고리즘으로 푸는 것이 좋다.

 

    2. 유클리드 호제법 (GCD구하기)

  유클리드 호제법은 두 정수의 최대공약수(GCD)를 구하는 방법으로 잘 알려져있고 이는 재귀 알고리즘으로 구현이 가능하다. 우선 유클리드 호제법이 무엇인가 먼저 알아보자.

  유클리드 호제법은 정수 a와 b의 GCD를 GCD(a,b)라 할때 GCD(a,b) = GCD(b,(a%b))를 이용하는 방법이다. 이번 정의도 재귀로 정의되므로 재귀 알고리즘으로 풀 수 있는 것이 보일 것이다. 그렇다면 언제까지 반복해야하는가? GCD(A,B)를 GCD 메서드의 형식이라 봤을 때 B가 0이되면 즉 비교하는 두 정수를 나눴을 때 나머지 값이 0이면 그때의 A값이 GCD가 된다. 정의를 정리해보면 '주어진 정수 a, b가 있을 때 a%b=0이면 b가 a, b의 GCD이다. 그렇지 않고 a%b!=0이면 GCD(a,b)=GCD(b,(a%b))이다.'가 된다. 이를 코드로 구현해보자.

static int GCD(int a, int b){
    if(a%b==0) return b;       // a%b=0이면 GCD= b
    else return GCD(b,a%b); // 그렇지 않으면 GCD(a,b) = GCD(b,a%b)
}

 다음과 같이 재귀 메서드가 완성되고 위에서 정의한 것을 그대로 옮긴 것 뿐이다.

 

• 재귀 알고리즘 분석하기

 분석을 하기위해 하나의 예시를 가져와 보겠다.

static void recur(int n){
    if(n>0) {
        recur(n - 1);
        System.out.println(n);
        recur(n - 2);
    }
}

 다음 recur 메서드는 n을 입력받고 n>0이면 3가지를 실행한다.

      1. recur(n-1)                    // 재귀 호출

      2. System.out.println(n)  // n 출력

      3. recur(n-2)                    // 재귀 호출 

 이렇게 메서드 안에 재귀 호출을 여러 번 실행하는 메서드를 순수 재귀라고 한다. 순수 재귀 메서드는 앞에서 봤던 단순한 재귀와 달리 한눈에 파악하고 이해하기 어렵다. 따라서 메서드가 어떻게 실행되는지 분석히야하는데 2가지 방법으로 분석할 수 있다.

 

 1) 하향식 분석

  하향식 분석(top-down analysis)은 가장 위쪽의 메서드부터 밑으로 분석해 내려가는 방법이다. recur(4)를 하향식 분석해 보면 recur(4)가 가장 위쪽의 메서드가 되고 recur(4)는 { [recur(3)], [4 출력],  [recur(2)] } 순서로 실행된다. 첫번째 순서인 recur(3)을 실행하니  recur(3)에 의해 { [recur(2)],  [3 출력],  [recur(1)] } 가 recur(4)의 다음 실행 순서인 [4 출력] 앞에 생겼고 실행 순서는 { [ [recur(2)],  [3 출력],  [recur(1)] ], [4 출력], [recur(2)] } 다음과 같이 변했다. 또  recur(2)를 실행하면 recur(3)때와 같이 앞쪽의 실행할 것들이 계속 늘어나고 이런식으로 가장 앞 순서인 것부터 차례로 실행해보면서 실제 코드가 진행대로 따라가보는 것이 하향식 분석이다. 하향식 분석으로 계속 따라가며 실행하다 보면 '1 2 3 1 4 1 2'가 한 줄에 한 글자씩 출력된다.

 

  2) 상향식 분석

   상향식 분석(bottom-up analysis)은 가장 아래의 메서드부터 올라가는 방법이다. recur(4)를 상향식 분석을 해보면 가장 아래인 recur(1)부터 구해야 한다(∵ n>0일때부터 메서드가 의미있게 실행되기 때문). recur(1)은 { [recur(0)] , [1 출력], [recur(-1)] }이 실행되고 recur(0)과 recur(-1)은 n<=0이므로 아무것도 실행되지 않으므로 recur(1)은 [1 출력]만을 수행한다( recur(1) : 1 출력). 그 다음인 recur(2)는 { [recur(1)], [2 출력], [recur(0)]}이 실행되고 recur(1)은 [1 출력]이고 recur(0)은 아무것도 실행되지 않으므로 recur(2) = { [1 출력], [2 출력] }이 된다. 이런 식으로 recur(3)을 구하고 recur(4)를 구하면 상향식 분석이 끝난다. 하향식 분석과 분석 결과는 똑같다.

 

• 재귀의 제거

 recur 메소드를 재귀 호출을 사용하지 않고 비재귀적으로 구현할 수도 있다. 

 

   1) 꼬리 재귀의 제거

 recur 메소드에서 3번째 실행 순서에 있는 recur(n-2)는 마지막 순서에서 재귀 호출을 하는 꼬리 재귀이므로 쉽게 제거할 수 있다. 예를 들면 recur(4)를 실행하면 { [recur(3)], [4 출력], [recur(2)] }가 실행되는데 [recur(3)]과 [4 출력]을 순서대로 실행을 완료했다면 [recur(2)]만 실행하면 되므로 다음과 같이 메서드를 바꿔도 같은 결과를 얻을 수 있다.

static void recur(int n){
    while(n>0) {
        recur(n - 1);
        System.out.println(n);
        n = n-2; //꼬리 재귀 제거
    }
}

 if를 while로 바꾸고 recur(n-2)를 n = n-2로 바꾸었다. recur(4)를 실행해보자. 먼저 while문으로 바뀌어도 조건은 같으므로 두번째 실행코드까지는 똑같이 진행된다. 이제 위에서 말한 것처럼 [recur(2)]만 실행하면 되는데 대신에 n = n-2가 있다. 이는 n을 n-2로 바꾸고 while문으로 처음부터 다시 실행해 recur(n-2)를 실행하는 것과 같은 효과를 준다. 

 

    2) 재귀의 제거

  꼬리 재귀는 마지막에 꼬리 재귀 혼자만 남아 문제없이 처리가 가능하다. 하지만 recur 메서드의 첫번째 재귀 호출처럼 뒤에 실행해야할 것이 많으면 어떻게 될까? 만약 꼬리 재귀때처럼 하면 뒤에있는 [n 출력], [recur(n-2)]는 n값이 변하기 때문에 올바른 결과값을 얻기 힘들다. 따라서 꼬리 재귀와 달리 스택을 이용해 알고리즘을 잘 구현해야 한다.

static void recur(int n){
    Stack<Integer> st = new Stack<>();
    while(true) {
        if(n>0) {
            st.push(n);
            n = n - 1;
            continue; 
        }
        if(!st.isEmpty()) {
            n = st.pop();
            System.out.println(n);
            n = n - 2;
        }else break;
    }
}

  recur(n)에서 실행해야할 것들이 [recur(n-1)], [n 출력], [recur(n-2)] 3가지있는데 앞에서부터 1번 실행문, 2번 실행문, 3번 실행문으로 부르겠다. 1번 실행문은 2번, 3번 실행문보다 우선순위가 높다고 생각하면 이해가 쉽다. 1번 실행문이 다 실행되고 나야 2번, 3번 실행문이 실행될 수 있으므로 첫번째 if문에서 n>0일경우(recur(n-1)이 실행될 경우) 1번 실행문만을 계속 반복한다. 하지만 이때 2번, 3번 실행문도 나중에 실행해야하므로 그때 필요한 n값을 미리 스택에 저장하며 반복한다. 우선순위가 높은 1번 실행문이 끝나면 다음 if문으로 넘어간다. 이제 저장해놨던 n값을 순서대로 pop하며 2번, 3번 실행문을 실행한다. 3번 실행문은 recur(n-2)이므로 처음부터 돌아가 n = n-2인 상태로 1번 실행문이 다시 실행된다. 따라서 3번 실행문이 실행되면 다시 우선순위가 높은 1번 실행문을 첫번째 if문의 조건을 만족하지 못할 때까지 반복한다. 이 과정을 반복하다 보면 스택에 아무것도 남지 않게 될때가 오는데 그때 while 반복문을 종료한다(메서드 종료).

 

• 메모화

  recur(4)를 재귀를 이용하여 구현하면 1 2 3 1 4 1 2 가 한줄 간격으로 출력되는 것을 알 수 있다. 이는 잘 생각해 보면 recur(1)이 3번 recur(2)가 2번 recur(3)이 1번 recur(4)가 1번 실행됐다는 것을 의미한다. recur(3), recur(4)의 경우는 상관없지만 recur(1), recur(2)의 경우는 똑같은 계산을 몇 번 반복해야하는데 똑같은 일을 반복적으로 하는 것을 매우 싫어하는 개발자들이 이를 가만히 둘리 없다. 메모화를 이용하면 recur(1)을 계산할 때 이 값을 저장해 놓고 나중에 recur(1) 값이 필요할 때 계산하지 않고 저장된 값을 가져와 중복계산을 없애줄 수 있다. 

import java.util.Scanner;
public class Main {
    static String[] memo;
    static void recur(int n){
        if (memo[n+1]!=null)
            System.out.print(memo[n+1]);
        else{
            if(n>0){
                recur(n-1);
                System.out.println(n);
                recur(n-2);
                memo[n+1]=memo[n]+n+"\n"+memo[n-1];
            }else {memo[n+1]="";}
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        memo = new String[n+2];
        recur(n);
    }
}

다음 코드가 메모화를 이용한 recur()메서드이다. memo 배열을 n+2크기로 만드는데 그 이유는 recur(-1) 부터 구현해야 하기 때문이다. 따라서 memo[0] = recur(-1), memo[1] = recur(0), memo[2] = recur(1), ... memo[n+1] = recur(n) 이 된다. 헷갈리니 잘 숙지하자. 배열을 생성한 뒤 recur(n)을 실행하면 먼저 if절이 나오고 조건식에 memo[n+1] != null 이 나온다. 이는 recur(n)이 실행된적이 있어서 값이 저장되어 있는가를 물어보는 식이다. 있다면 굳이 아래 else절을 실행할 필요없이 memo[n+1]을 출력하고 끝낸다. 하지만 처음엔 memo배열의 모든 요소가 null이므로 else절로 넘어가자(한번 실행이 된적이 있어야 memo에 null값이 없어짐). else절은 맨 처음 배웠던 코드랑 크게 다르지 않다. 다른점이 있다면 recur(n-2)까지 끝내고 그 결과를 저장 한다는 것이다(메모화). memo[n+1] = memo[n]+n+"\n"+memo[n-1]는 recur(n)의 실행결과를  memo[n+1]에 저장하는 것이다. 실행 결과는 recur(n-1)의 결과에 "n+\n"을 더하고 recur(n-2)의 결과를 더한 값이다 . n값이 뒤죽박죽이라 헷갈릴 수 있는데 천천히 생각해보면 recur(n-1)+n+"\n"+recur(n-2)라는 뜻이다. 만약 n>0을 만족하지 못하면 else절로 넘어간다. 즉 n=0, n=-1 일때  n>0를 만족하지 못해서 else절로 넘어가는데 이때 memo[1], memo[0]은 recur(0), recur(-1) 이므로 그냥 빈 문자열을 저장한다(recur(0)과 recur(-1)은 아무것도 실행되지 않으므로).

 

 간단하게 정리하면 다음과 같다.

 

    1. 메서드를 실행한다.

    2. 저장된 값이 있는지 확인하고 있으면 저장된 값을 출력한다.

    3. 저장된 값이 없으면 계산을 시작한다.

    4. 계산이 끝나면 값을 저장한다.

    5. 재귀 호출이 있으면 다시 1부터 시작한다.

 

 메모화를 한 경우 recur 메서드의 재귀 호출이 줄어들 것이다. 메모화가 있는 버전과 없는 버전의 recur 메서드 호출 횟수를 비교해보자.

메모화	n=1	n=2	n=3	n=4	n=5	n=6	n=7	n=8	n=9
X	3	5	9	15	25	41	67	109	177
O	3	5	7	9	11	13	15	17	19

 확실히 메모화를 했을때 recur 메서드 호출이 줄어들고 이는 recur 메서드 안에 재귀 호출이 2번 더 있으므로 실제로 표에서 보는 것과 같이 n이 커질 수록 호출 횟수가 크게 차이가 난다. 따라서 재귀 메서드를 쓸일이 있으면 메모화를 고려해 보는 것이 훨씬 효율적인 것을 알 수 있다.