재귀함수의 활용

프로그래밍을 처음 배울때부터 재귀함수라는 것을 배우긴 하지만, 대개는 굳이 재귀함수가 아니어도 풀어 낼 수 있는 예제로 재귀함수를 배우게 된다. 그렇다보니 재귀함수를 왜 써야 하는지, 그리고 어떻게 써야 하는지에 대해 이해하지 못하고 넘어가는 경우가 많은 것 같다. 피보나치 수열이나 팩토리얼 문제 같은 것들이 전형적인 예제 인것 같은데, 사실 해당 예제들은 반복문으로도 얼마든지 풀 수 있고 재귀함수는 성능저하나 stack오버플로우를 유발할 수 있기에, 실무에서나 문제풀이상황에서 굳이  재귀함수를 쓸 필요가 없을 것 같다.

 

그래서 이 글에서는 재귀함수가 아니면 문제를 해결하기가 어려운 "조합" 문제를 통해서 재귀함수가 필요한 이유와 재귀함수를 어떻게 단계적으로 접근해 나가야 하는지 적어보고자 한다. 예시코드는 java코드를 사용할 예정이다.

 

일단, 아래와 같은 문제 상황이 주어졌다고 가정해보자.

//        다음 배열을 2개의 숫자로 조합할수 있는 경우의 수는?
        int[] arr = {10, 20, 30, 40};
        for(int i=0; i<arr.length; i++){
            for(int j=i+1; j<arr.length; j++){
                System.out.println(arr[i]+" "+arr[j]);
            }
        }

2중 for문을 돌려서 print를 하든 배열에 담아내든 하면 되니, 너무 쉽다. 3개의 숫자로 조합을 해야 한다면, 3번의 반복문이 있다면 해결이 될 것이다. 그렇다면 2개 또는 3개의 숫자로의 조합이 아닌 n개의 숫자로의 조합을 해야한다면 어떻게 해야할까? input값으로 반복문의 횟수가 결정된다면, 위와 같은 방식으로 반복문을 코딩하는게 불가능하다.

 

즉, 반복문의 깊이가 예상되지 않는 상황이라면 반복문자체를 n번 호출하는 재귀함수가 아니고는 문제를 해결하기가 어렵다.

 

재귀함수를 코딩하기 전에 어떻게 단계적으로 재귀함수에 접근해야 하는지에 대해 적어보고자 한다.

 

일단 위의 문제를 조금 바꿔서 2개,3개 조합에 더해서 1개 조합, 4개 조합 등 주어진 숫자로 조합할 수 있는 경우의 배열을 출력해보자.(10 20과 20 10 등의 중복은 허용하는 조합) 재귀함수로 고치기 전에, 다소 무식한 for문으로 코딩을 해보자.  숫자 1개로 이루어져있는 조합, 숫자2개로 이루어져있는 조합, 3개, 4개로 이루어져있는 조합이 나올 것이다. 어찌됐든 반복횟수가 명확히 주어져 있는 상황이라면 무식하긴 하지만 아래와 같이 무식한 코딩이 가능은 할 것이다.

 

for문 형식1.

//        숫자 1개의 조합
        int[] arr = {10, 20, 30, 40};
        for(int i=0; i<arr.length; i++){
            System.out.println(arr[i]);
        }

//        숫자 2개의 조합
        for(int i=0; i<arr.length; i++){
            for(int j=i+1; j<arr.length; j++){
                System.out.println(arr[i]+" "+arr[j]);
            }
        }
//        숫자 3개의 조합
        for(int i=0; i<arr.length; i++){
            for(int j=i+1; j<arr.length; j++){
                for(int k=j+1; k<arr.length; k++){
                    System.out.println(arr[i]+" "+arr[j]+" "+arr[k]);
                }
            }
        }
//		  4개 조합 생략

 

일단, 깊이를 알수 없는 for문 반복이 발생하는 코드이라면, 뭔가 재귀함수로 바꾸긴 해야 할것 같은데, 어떤식으로 접근해야 할지 어려움을 겪을 것이다. 그럴땐 일단 무식하게 코딩을 1set 해두고, 해당 코드를 module화 시킬 수 있는 방법을 찾아야 한다. 위 코드는 값을 문자열로 더해서 프린트 시켜 버리니 다소 모듈화를 시키기 어려우므로 아래와 같이 코드를 한번 변경해보자.

 

for문 형식2.

        int[] arr = {10, 20, 30, 40};

//        1개짜리 배열
        int[] new_arr = new int[1];
        int num = 0;
        for(int i=0; i<arr.length; i++){
            new_arr[num] = arr[i];
            System.out.println(Arrays.toString(new_arr));
        }

//        2개짜리 배열
        int[] new_arr = new int[2];
        for(int i=0; i<arr.length; i++){
            int num = 0;
            new_arr[num] = arr[i];
            for(int j=i+1; j<arr.length; j++){
                num = 1;
                new_arr[num] = arr[j];
                System.out.println(Arrays.toString(new_arr));
            }
        }

//        3개짜리 배열
        int[] new_arr = new int[3];
        for(int i=0; i<arr.length; i++){
            int num = 0;
            new_arr[num] = arr[i];
            for(int j=i+1; j<arr.length; j++){
                num = 1;
                new_arr[num] = arr[j];
                for(int k=j+1; k<arr.length; k++){
                    num = 2;
                    new_arr[num] = arr[k];
                    System.out.println(Arrays.toString(new_arr));
                }
            }
        }
        
//        4개짜리 생략

 

어떤 생각을 가지고 코드를 위와 같이 변경했는지 이해가 되는가? for문 안에 똑같은 형식의 for문을 만들어줘야지, 해당 포문을 모듈화 시킬 수가 있다. 재귀함수의 기본은 함수안에서 자기자신을 다시 호출하는 것이므로, for문을 활용해 재귀문을 짤때 그 형식이 같아야지 반복 가능한 재귀함수가 될 수 있다. 이제 재귀함수 코드를 짜보자. 이해가 안되면 일단 스크로를 내려보자.

 

재귀함수

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40};
        for(int i=1; i<=arr.length; i++){
            recur(arr, new int[i], 0, 0);
        }
    }
    
    static void recur(int[] arr, int[] new_arr, int start, int num){
        if(num == new_arr.length){
            System.out.println(Arrays.toString(new_arr));
            return;
        }
        for(int i=start; i<arr.length; i++){
            new_arr[num] = arr[i];
            recur(arr, new_arr, i+1, num+1);
        }
    }

 

재귀함수는 무식한 for문 중에 형식2라고 명명지은 모듈화된 for문을 가지고 그 내용을 참고하여 만들어 가면 된다. 아래와 같이 단계적으로 접근해보자.

 

1)먼저, 형식2의 for문을 보면, for문 안에서 for문이 반복되고 있으니, 재귀함수에서 for문은 한셋만 만들고, 그 안에서 해당 for문이 다시 호출 되도록 recur함수를 호출할수 있게 코딩한다.

2)매개변수로는 원본 arr에서 계속해 값을 가져와야하므로, 첫번째 매개변수로 arr을 전달한다.

3)다음으로 1개,2개,3개,4개 등 조합을 가진 배열에 값을 세팅하고, 출력할 것이므로 main함수에서 recur를 호출할때 new int[i]값을 두번째 매개변수로 전달한다.

4)세번째 매개변수인 start는 형식2의 for문에서 i=0부터 시작하여, i+1, j+1 등으로 start 값이 변화하는 것을 반영한 것이다. 최초값을 0으로 주고 recur를 호출할때마다 i+1로 값을 바꿔 호출한다.

5)마지막 매개변수 num은 형식2의 for문을 보면, i번 for문, j번 for문 등 1씩 증가하는 형태의 값이다. 그러므로, recur를 호출할때마다 1씩 늘려가면서 호출하게 된다.

6)재귀문 안의 if문의 경우, num은 최초 지정한 new_arr의 길이를 넘어갈 수는 없으므로, 해당 길이에 도달할 경우 return하게 한다. return하면서 동시에 해당 if문 안에서 배열을 출력하도록 한다.

 

사실 재귀함수가 이해하기 어려운 이유는 깊어지는 재귀함수 상황에서 value값이 어떻게 변화하는지 머릿속으로 시뮬레이션 하는 과정이 어렵기 때문이다. 재귀함수를 이해하는 것은 글과 말로 설명하기는 어려운 본인만의 시뮬레이션 영역이다. 간단한 테스트케이스로 값을 전부 메모장에 적어보거나, 머릿속으로 시뮬레이션을 해야만 한다. 그러나, 위와 같이 일단 무식한 for문을 먼저 짜고 나서 재귀함수를 만들어본다면 시뮬레이션하는데 크게 도움이 될 것이라고 생각한다. 위 무식한 for문의 실행흐름이 재귀함수와 동일하기 때문에 머릿속으로 시뮬레이션 하는데 도움이 될 것이다.

 

정리하자면, 재귀함수를 써야할것만 같은 상황을 만나게 된다면 일단 주어진 테스트케이스로 무식하게 for문을 짜보자. 그다음에 해당 for문을 뭔가 반복이 가능하도록 모듈화 시키는 작업을 거치자. 그다음에 해당 모듈화된 for문을 테스트케이스와 무관하게 input값에 따라 반복이 될 수 있는 재귀함수 형태로 바꿔보자.