자바로 살펴본 재귀 함수의 동작 방법 - 2 (Java Recursive method with 순열)

 

자바로 살펴보는 재귀함수의 동작방법 두번째 입니다.  : - )

재귀함수를 사용하는 이유는 반복문과 비교문을 통해서 해결하기 어렵거나 복잡한 기능을 간단하게 완성시키는데 목적이 있습니다.

물론 머리가 좋은 사람들은 반복문과 비교문만 활용해서 훌륭하게 만들수도 있겠지만요..

 

이번에 살펴볼 기능은 순열 알고리즘(Permutation Algorithm) 입니다.

순열이라는 뜻은 어떠한 데이터의 순서를 겹치지 않게 나열한 개수를 의미 합니다.

숫자 1,2를 가지고 표현 가능한 방법은 2가지 입니다.
 1) 1, 2
 2) 2, 1

숫자 1,2,3을 가지고 표현할 수 있는 방법은 6가지 입니다.
 1) 1, 2, 3
 2) 1, 3, 2
 3) 2, 1, 3
 4) 2, 3, 1
 5) 3, 2, 1
 6) 3, 1, 2

 

숫자가 두세개인 경우에는 사실 머릿속으로 계산하여 바로바로 나올 수 있겠지만..갯수가 n개인 경우에는 그 가지수를 구하는 것은 매우 어렵습니다.

과연 조건문과 반복문만 가지고 기능을 구현 할 수 있을까요?

 

이를 쉽게 해결하기 위해 필요한 방법이 바로 재귀(Recursive) 알고리즘을 통한 문제접근 입니다.

재귀(Recursive)의 개념 접근의 첫번째 방법은, 마지막 호출이 될 때 까지 동작한 다음에 역순으로 되돌아와 끝난다는 것 입니다.

설명을 위해서 완성된 코드를 먼저 살펴 봅니다.

import java.util.Arrays;

public class TestClass {
    public static void main(String[] args) {
        int arr[] = {1,2,3};
        permutation(arr, 0, 3);
    }

    public static void permutation(int[] arr, int depth, int r) {
        if (depth == r) {  
            print(arr, r);
            return; //종료
        }
        for (int i=depth; i<arr.length; i++) {
            swap(arr, depth, i); //순서 변경
            permutation(arr, depth + 1, r);  //아래로 탐색
            swap(arr, depth, i);  //되돌리기
        }
    }
	
    public static void swap(int[] arr, int depth, int i) {
        int temp = arr[depth];
        arr[depth] = arr[i];
        arr[i] = temp;
    }
	
    public static void print(int[] arr, int r) {
        int printArr [] = arr.clone();
        if(printArr.length > r) {
            for(int i=0;i < printArr.length;i++) {
                if(i+1 > r) {
                    printArr[i] = -1;
                }
            }
        }
        System.out.println("Array : " + Arrays.toString(printArr));
    }

}

 

print 메소드는 단순히 출력을 위한 메소드이며, 나머지 permutation 메소드와 swap 메소드가 실제 순열에 사용되는 메소드 입니다.

permutation 에서 arr은 대상 배열이며, depth은 단계 입니다. 그리고 r은 선택 하는 가지수 입니다.

swap 메소드는 배열의 값을 바꾸는 데 사용되는 메소드 이므로 이해하는 데 어렵지가 않습니다.

여기서 핵심인 메소드가 permutation 메소드 입니다.

 

permutation메소드에서 가장 처음 들어오는 값은 depth = 0, r = 3 입니다.

depth라는 값은 r과 처음에 같지 않으므로 return되지 않습니다.

그리고 나서 반복문을 만나며 재귀호출에 들어가게 됩니다.

여기까지의 값을 살펴 보면 아래와 같습니다.

int depth = 0
int r = 3
(반복문 변수) int i = 0

 

잊지 말아야 되는 내용은 "깊게 쭉 들어간 다음에 역순으로 나온다" 입니다.

반복문 for에 의해서 pemutation이 계속되서 호출되고 return에 의해서 종료 될 때 까지 깊게, 마지막까지 pemutation을 호출 하여야 합니다.

아래 글로 표현한 내용을 한번 살펴 봅니다.

#1. 처음 permutation에 진입함
 int depth = 0
 int r = 3
 (반복문 변수) int i = 0

#2. #1번에서의 반복문에 의해서 permutation에 진입함
  int depth = 1
  int r = 3
  (반복문 변수) int i = 1  
  
#3. #2번에서의 반복문에 의해서 permutation에 진입함  
  int depth = 2
  int r = 3
  (반복문 변수) int i = 2 
  
#4. #3번에 의해서 permutation에 진입함
  int depth = 3
  int r = 3
  depth가 r과 같으므로 break!!
  
...

 

이처럼 끝까지 단계를 밟고 나간뒤에 거꾸로 돌아오는 것에 대해서 익숙해져야 합니다.

이를 그림으로 표현하여 보면,

여기서 주목해야되는 것이 4~5번 구간 입니다.

 

3번 구간은 return을 통해 재귀의 끝을 알리는 구간 입니다.

그러므로 depth가 2 이면서 i가 2인 곳에 다시 돌아오게 됩니다.

그 곳에서 i는 다시 증가를 하지만 i 값이 3으로 증가하게 되므로 반복문이 더 이상 동작하지 않고 종료가 되었습니다.

그리고 나서 depth가 1이면서 i가 1인곳인 2번구간에 되돌아 오게 됩니다.

 

이 4번과 5번 구간을 이해 하는 것이 가장 중요 합니다.

가장 깊게 들어간 뒤에 역순으로 다시 되돌아와 남겨진 행동을 다시하고 있기 때문 입니다.

 

5번구간이 끝나고 난 뒤에 6번구간에 진입을 합니다.

이때 depth는 1의 값을 가지고 있으며, i는 2의 값을 가지고 있습니다.

swap 이라는 메소드가 호출되면서 배열의 1번과 2번의 서로의 순서가 6번구간에서 바뀌게 됩니다.

 

그리고 다시 7번구간에서는 depth값이 3으로 증가된 상태이므로 8번 상태인 return되게 되며 6번구간에 다시 되돌아 오게 됩니다.

그러면서 또 다시 swap이라는 메소드가 호출되면서 배열의 1번과 2번의 서로의 순서가 원래대로 되돌아 오게 됩니다.

 

swap이라는 메소드가 반복문에서 2번 호출 된 이유가 바로 이것입니다.

기존의 배열 순서를 원래대로 되돌려야 다음 단계에서도 순서가 보장되기 때문 입니다.

 * 전문 용어로 백 트래킹이라고 한다고 합니다.

 

나누어서 단계별로 살펴 보았으니 1,2,3 이라는 배열 값이 최종적으로 어떻게 서로 순서가 바뀌는지 전체 모습을 한번 살펴 보겠습니다.

주황색 구간에서 메소드가 return 됩니다. 물론 print 메소드를 이때 호출하게 됩니다.

 

배열의 갯수와 선택 해야하는 개수를 바꾼다 하더라도 위 단계에 따라 동작하게 될 것 입니다.

물론 모든 경우의 수를 전부 수행하므로 컴퓨터가 고생해야 되는 시간은 개수가 늘어날 수록 마찬가지로 늘어나겠지요.

 

이상으로 순열을 통하여 재귀 함수의 동작 방법에 대해서 살펴 보았습니다.

궁금한점, 틀린부분은 언제든 댓글 또는 메일로 연락주세요!  👻

 

* 자바로 살펴본 재귀 함수의 동작 방법 - 1 (https://lts0606.tistory.com/509)