[Java] 재귀함수 작성 방법 - 예제와 2가지 고려사항

Cos Pro 샘플 문제 4차 8번은 재귀함수를 작성하는 문제입니다. 너무 복잡해서 이해도 되지 않고, 시험에서 재귀함수를 작성하라는 문제가 나오면 어떻게 풀지 막막해서 재귀함수에 대해 정리해보려고 합니다. 

※ 이 내용은 알고리즘 문제 해결 전략(인사이트, 구종만 지음)을 참고하였습니다. 인용 표시가 들어가는 부분은 책의 내용을 그대로 옮겼습니다.

재귀함수???

우리가 코딩을 할 때, 코드 중 공통적으로 반복되는 부분을 발견할 수 있습니다. 이런 부분은 for문 등으로 묶어서 수행하게 할 수 있지요. 재귀함수는 이런 반복적인 작업을 구현할 때 유용하게 사용되는 개념입니다.

재귀함수란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킵니다. 

 

재귀함수 작성하기-1부터 n까지의 숫자 더하기

다음은 간단한 재귀함수를 작성하고 어떻게 작성해야 하는지 고민해보겠습니다.

public class RecursiveFunction{
    //1부터 n까지의 합을 계산하는 함수
    public int sum(int n){
        int answer=0;
        for(int i=1;i<=n;i++){
            answer+=i;
        }
        return answer;
    }

    public static void main(String[] args){
        int n=10;
        RecursiveFunction rf = new RecursiveFunction();
        System.out.println("1부터 10까지의 합(for문) : "+ rf.sum(n));
    }
}

//출력결과
1부터 10까지의 합(for문) : 55

sum() 함수는 for문을 이용해 1부터 n까지의 합을 구하는 함수입니다. 이것을 어떻게 재귀함수로 바꿀지 고민해보겠습니다. 앞서 재귀함수의 정의에서 작업을 여러 조각으로 쪼갠다고 했는데요. sum() 함수의 가장 작은 조각은 answer+=i 부분입니다. 앞서의 결과에 i를 더하는 부분입니다. 이때, answer와 i 둘 중 하나를 자기 자신을 호출해서 사용하고, 하나는 그대로 더해주면 됩니다. 여기서 어느 부분을 자기 자신을 호출해서 사용할지를 판단하는 것이 중요하다고 하겠습니다.

sum()을 풀어보면  다음과 같이 쓸 수 있습니다.

sum(n)    = 1+2+3+... n-2+n-1+n
sum(n-1) = 1+2+3+... n-3+n-2+n-1
sum(n-2) = 1+2+3+... n-4+n-3+n-2

즉, sum(n) = sum(n-1)+n으로 표시되므로 sum(n)을 자기 자신을 이용할 수 있습니다.
따라서 answer+=i의 answer는 sum(n-1)으로 재귀 호출이 가능하고, i는 n이 됩니다.
반대로 sum(n) = 1+ (2+3+... n)과 같은 형태로 앞을 자르면 뒷부분이 재귀 함수 형태로 만들 수 없기 때문에 원하는 답을 낼 수 없습니다. 

이 것을 고려해서 아래와 같이 재귀함수 recursiveSum()을 만들었습니다.

public class RecursiveFunction{    
    //1부터 n까지의 합을 계산하는 재귀함수
    public int recursiveSum(int n){
        if(n==1) return 1;  //더이상 쪼개지지 않는 지점에서 값을 반환합니다.
        return recursiveSum(n-1)+n;
    }

    public static void main(String[] args){
        int n=10;
        RecursiveFunction rf = new RecursiveFunction();

        System.out.println("1부터 10까지의 합(재귀함수) : "+ rf.recursiveSum(n));
    }
}

//출력결과
1부터 10까지의 합(재귀함수) : 55

우선 첫 번째 줄의 if문을 볼 텐데요. 책에서는 이 부분을 가리켜 아래와 같이 언급하고 있습니다.

재귀함수는 더 이상 쪼개지지 않는 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 합니다. 이때 쪼개지지 않는 가장 작은 작업들을 가리켜 재귀 호출의 기저사례(base case)라고 합니다.

이것이 재귀함수에서 가장 첫 번째로 고려해야 하는 기저 사례입니다. 이 기저 사례에 따라 재귀호출을 중단하지 않으면 재귀함수는 무한히 자신을 호출하게 됩니다. 여기에서 기저 사례는 n부터 1씩 감소하여 더 이상 감소하지 않는 1이 되었을 때입니다. 그리고 이 기저 사례를 선택할 때는 모든 입력이(위 사례에서는 n) 항상 이 종료 조건을 만족시키는 것이 가능하도록 고려해야 합니다. 만약 여기에서 n이 2일 때 3을 반환한다고 종료 조건을 설정하면, n=1인 경우에 오류가 발생합니다. 그리고 재귀호출 시에 기저사례에 도달할 수 있도록 해당하는 값을 감소 또는 증가시켜야 합니다.

728x90

 

재귀 함수 작성하기 - 중첩 반복문 대체 하기

이번에는 난이도를 높여서 중첩 반복문을 재귀 함수로 만들어보겠습니다. 0부터 n까지의 숫자 중 4개를 중복 없이 고르는 모든 경우를 출력하는 코드를 작성해보겠습니다. 우선 중첩 for문으로 작성합니다.

import java.util.ArrayList;

public class RecursiveFunction{
    //1부터 n까지의 수중 4개 고르는 모든 방법을 찾는 함수
    //숫자 네개를 문자로 출력
    public ArrayList<String> pick(int n){
        ArrayList<String> pickArray = new ArrayList<>();
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                for(int k=j+1;k<=n;k++){
                    for(int l=k+1;l<=n;l++){
                        String pickStr;
                        pickStr=Integer.toString(i)+Integer.toString(j)+Integer.toString(k)+Integer.toString(l);
                        pickArray.add(pickStr);
                    }
                }
            }
        }
        return pickArray;
    }

    public static void main(String[] args){
        int n=6;
        RecursiveFunction rf = new RecursiveFunction();

        ArrayList<String> pickStr = rf.pick(n);
        System.out.println("1부터 n까지의 숫자중 4개를 선택하여 모두 출력: 총 "+ pickStr.size()+"개/"+ pickStr.toString());
    }
}

//출력결과
1부터 n까지의 숫자중 4개를 선택하여 모두 출력: 총 15개/[1234, 1235, 1236, 1245, 1246, 1256, 1345, 1346, 1356, 1456, 2345, 2346, 2356, 2456, 3456]

 

위와 같이 for문을 반복하는 것은 직관적으로 이해가 쉽습니다. 만약 5개의 숫자를 고른다면 for문을 5개 쓰면 되고, 6개 숫자를 고른다면 for문을 6개 쓰면 됩니다. 하지만 계속 골라야 하는 원소의 수가 늘어난다면 코드가 너무 길고 복잡해지고, 더구나, 골라야 하는 원소의 개수를 입력받는 경우에는 사용할 수 없다는 문제가 있습니다. 이런 경우에 재귀함수를 사용하면 코드가 간결해질 수 있습니다.

그럼 위의 pick() 함수를 재귀함수 recursivePick(int n, String picked, int maxNum, int cnt)으로 만들어보겠습니다.
인자 값은 다음과 같습니다.

n: 선택 가능한 숫자 값
picked: 재귀함수에 전달하는 이미 선택된 숫자열
maxNum:선택된 숫자의 최대값
cnt: 선택할 숫자의 개수(여기서는 4)

n과 cnt는 앞서 와 동일한데, 재귀함수에 전달하기 위해 picked를 추가하였습니다.
그리고, 중복을 허용하지 않기 때문에, 숫자열은 항상 숫자의 오름차순으로 만들어집니다. 그래서 앞서 사용한 숫자를 사용하지 않기 위해 maxNum을 추가하였습니다.

그래서 작성한 재귀함수는 다음과 같습니다.

import java.util.ArrayList;

public class RecursiveFunction{

	//재귀호출의 결과를 저장하기 위한 전역 변수
    ArrayList<String> recursivePickStr = new ArrayList<>(); 
    //1부터 n까지의 수중 4개 고르는 모든 방법을 찾는 재귀 함수
    //숫자 네개를 문자로 출력
    public void recursivePick(int n, String picked,int maxNum, int cnt){
        //기저사례: cnt를 1씩 줄여 숫자 4개를 모두 선택했으면,재귀호출을 종료한다.
        if(cnt==0){
            recursivePickStr.add(picked); //전역변수에 문자열을 추가한다.
            return;
        }
        //1부터 n까지의 숫자 중에서 pick을 한다.
        //중복을 허용하지 않으면, 항상 뒷자리가 앞자리보다 크므로 재귀호출 시 for문은 maxNum+1부터 시작한다.
        for(int i=maxNum+1;i<=n;i++){
        	//picked에 for문의 i를 추가하여 재귀호출한다. maxNum과 cnt를 인자로 전달한다.
            recursivePick(n,picked+Integer.toString(i),i,cnt-1); 
        }
    }


    public static void main(String[] args){
        int n=6;
        RecursiveFunction rf = new RecursiveFunction();
        
        rf.recursivePick(n,"",0,4); //최초값 설정하여 입력
        System.out.println("1부터 n까지의 숫자중 4개를 선택하여 모두 출력: 총 "+ rf.recursivePickStr.size()+"개/"+ rf.recursivePickStr.toString());
    }
}

재귀함수를 보시면, 반환 값이 void로 없습니다.
여기서 재귀함수의 두 번째 고려사항이 나옵니다. 앞서 1부터 n까지의 합을 구할 때는 재귀함수의 반환값을 이전에 호출된 재귀함수가 받아서 사용했습니다. 즉, 재귀호출이 기저사례를 만나서 종료되면, 역방향으로 반환값이 전달되어 최종 결과가 나왔습니다.

그런데, 이번에는 반환값을 사용하지 않고, 재귀함수의 인자로 현재 값을 넣어주어 최종 결과를 전역 변수에 저장했습니다. 이것은 정방향으로 진행한 재귀함수입니다. 

이렇게, 재귀함수를 작성할 때, 재귀호출을 반복하고 기저 사례를 만나면 값을 반환해서 역방향으로 결과를 낼지, 아니면 정방향으로 재귀호출하고 그 끝에 그 시점에 결과를 낼지 결정하는 것이 두 번째 고려사항입니다.

(참고한 블로그에서는 정방향과 역방향, 반환 값있음, 없음을 각각 분리해서 두 번째, 세 번째 고려사항으로 설명했지만, 저는 합치는 것이 더 이해가 나은 것 같아서 합쳤습니다.)

그리고 제가 했던 실수가 있어서 공유드리겠습니다.
중첩 반복문 케이스에서는 for문 안에서 재귀함수를 여러번 호출하게 됩니다. 즉 같은 호출 레벨에서 호출하는 것이기 때문에 입력되는 인자도 같은 레벨이어야 합니다.
위 예에서 처음에 두번째 인자인 picked의 값을 함수 밖에서 계산해서 넣으니, 다음 for문에서 변경된 picked의 값을 사용하는 문제가 있었습니다. 이 부분을 주의해서 재귀함수를 구현해야겠습니다.

다시 정리하면...

앞서 두 개의 예제로 두 가지 고려사항을 알아보았습니다.

첫째, 재귀호출을 종료시키는 기저사례를 찾고, 기저사례에 도달하도록 값을 변화시킬 것

둘째, 재귀호출의 반환값을 사용할지, 재귀호출의 반환 없이 종료할 것인지 결정할 것

재귀함수는 간결한 코드를 위해 꼭 익혀두어야 합니다. 포스팅이 학습하시는 분들께 도움이 되면 좋습니다.

참고자료

- 책: 알고리즘 문제 해결 전략(인사이트, 구종만 지음)
- 웹페이지: 재귀함수 예제로 이해하기, 3가지 규칙