자바 재귀 호출은 무엇인가? : factorial, 거듭제곱의 합 구하기

 

메서드의 내부에서 스스로를 재호출하는 것을 재귀호출이라고 한다.

물론 스스로 계속해서 호출하기만 한다면 callStack을 가득 채우게 되어서 StackOverFlow 에러를 보게 될 것이다.

따라서 필수적으로 조건문이 붙어야 한다. 

 

 

엥? 별다른 지정해주지 않으면 계속 반복하고 조건문으로 제어해줘야 한다고? 그냥 반복문 아닌가?

그렇다. 반복문은 명령만을 반복해서 수행한다면 재귀 호출은 메소드를 직접적으로 반복 호출하는 형태이다.

 

그러나 재귀 호출 시에는 메서드를 계속해서 호출하기 때문에 CallStack의 메모리 공간을 계속해서 사용하게 되기 때문에 성능면에서 반복문보다 좋지 않다. (사용하는 언어의 컴파일러가 꼬리재귀를 지원한다면 꼬리재귀의 사용으로 이런 단점을 극복할 수 있으나 이 글에서는 다루지 않는다. )

 

그렇다면 왜 재귀 함수를 사용하는 것일까?

1. 불필요한 변수 생성을 하지 않아도 된다.

2. 반복문보다 코드가 간결해진다.

3. 알고리즘에 재귀가 유리한 경우가 있다.

( ex > 피보나치 수열 )

 

그렇다고 합니다.

아래는 대표적인 재귀 함수의 예제인 팩토리얼이다.

( 팩토리얼은 1부터 n까지 차례로 곱하는 것을 의미한다. )

public class Factorial {
    static long calculate(long num) {
        if (num == 0) return 0; // 만약 0이 num에 들어갈 경우 무한 재귀로 StackOverFlow
        if (num == 1) return 1;
        return num = num * calculate(--num);
    }

    public static void main(String[] args) {
        long result = calculate(5);
        System.out.println(result);

        for (int i=0; i<21; i++) {
            long result2 = calculate(i);
            System.out.println(i + "! = " + result2);
        }
    }
}

 

calculate() 메서드에 21이 대입되었을 때의 상황을 그림으로 표현하면 아래와 같다.

 

main()이 항상 제일 먼저 호출되어 콜스택에 쌓이고 calculate(21) 메서드가 호출 calculate(20) .. calculate(19) .. .. calculate(1) .. 까지 호출되면 재귀가 끝나고 1을 return한다.

그러면 이번에는 반대로 calculate(2) calculate(3) .. .. .. calculate(21)까지 실행되어 result에 값을 반환한다.

사실 그림으로 보면서 설명을 읽으면 너무 쉽게 느껴지는데 막상 내가 코드를 작성하려고 하면 조금 헷갈린다.

 

다음은 조금 더 난이도가 높은(?) 거듭제곱의 합 구하기다.

 

public class Square {
    public static long sum(int num, int n) {
        if ( n == 1 ) return num;
        return num * sum(num,--n);
    }
    // 제곱을 구하는 메소드

    public static void main(String[] args) {
        int n = 5;
        long result = 0;

        System.out.println(sum(2,5));

        for ( int i=1; i<n; i++) {
            result += sum(2,i);
            System.out.println(result);
        }
        // 2의 n제곱을 각각 더하는 반복문
    }
}

 

위와 크게 다른 것은 없으나 이번에는 매개변수가 두개라서 조금 혼란이 올 수도 있다.

제곱과 합을 동시에 한 개의 메서드에서 해결할 수는 없고 재귀 함수 두 개를 사용하거나 더하는 것만 반복문을 사용해도 된다.

물론 간단한 문제이기 때문에 애초에 재귀를 사용하지 않고 반복문으로만 해결해도 아무 문제가 없을 것이다.