재귀

mingseok·2022년 5월 14일

목록 보기

4/10

메서드의 내부에서 메서드 자신을 다시 호출하는 것을 ‘재귀호출’ 이라 하고,
재귀호출을 하는 메서드를 ‘재귀 메서드’ 라 한다.

void method() {  
   Method();
}

호출된 메서드는 ‘값에 의한 호출’ 을 통해, 원래의 값이 아닌 복사된 값으로 작업하기 때문에
호출한 메서드와 관계없이 독립적인 작업 수행이 가능하다.

재귀호출도 조건문이 필수적으로 따라 다닌다.

왜? 굳이 반복문대신 재귀호출을 사용할까?

몇 겹의 반복문과 조건문으로 복잡하게 작성된 코드가 재귀호출로 작성하면 보다
단순한 구조로 바뀔 수도 있다.

대표적인 재귀호출 예는 팩토리얼이다.

팩토리얼은 한 숫자가 1이 될 때까지 1씩 감소 시켜가며 계속해서 곱해 나가는 것인데
예를 들면, ‘5! = 5 4 3 2 1 = 120’ 이다.

팩토리얼 예제.

class aaa {

    public static void main(String[] args) {

        int result = factorial(4);
        System.out.println(result);

    }

    static int factorial(int n) {
        int result = 0;
        if (n == 1) {
            result = 1;
        } else {
            result = n * factorial(n - 1);
        }
        return result;

    }

}

// 실행 결과 : 24

factorial메서드가 static 메서드이므로 인스턴스를 생성하지 않고 직접 호출할 수 있다.

그리고 main 메서드와 같은 클래스에 있기 때문에 static 메서드를 호출할 때 클래스이름을
생략하는 것이 가능하다. 그래서 aaa.factorial(4) 대신 factorial(4) 와 같이 하였다.

factorial( 2 ) 를 호출했을 때의 실행과정이라고 생각해보자.

static int factorial(int n) {
        if (n == 1) {
            result = 1;
        }
        return n * factorial(n - 1);

    }

factorial( 2 ) 를 호출하면서 매개변수 n에 2가 복사된다.
‘return n * factorial(n - 1);’ 을 계산하려면 factorial( 1 ) 을 호출한 결과가 필요하다.

그래서 factorial( 1 ) 이 호출되고 매개변수 n에 1이 복사된다.
if문의 조건식이 참이므로 1을 반환하면서 메서드는 종료된다. 그리고 factorial( 1 ) 을 호출한 곳으로 되돌아 간다.
이제 factorial( 1 ) 의 결과값인 1을 얻었으므로, return 문이 다음의 과정으로 계산된다.

return 2 * factorial( 1 );

→ return 2 * 1;

→ return 2;

메서드 값이 0이면 어떻게 될까? 또는 100,000 과 같이 큰 수이면 어떻게 될까?

n의 값이 0인 경우는 if문의 조건식이 절대 참이 될 수 없기 때문에 계속 해서 재귀호출만 일어날 뿐
메서드가 종료되지 않으므로 스택에 계속 데이터가 쌓여만 가면서, 결국 저장한계를 넘게 되고, ‘스택오버플로우 에러가 발생한다.

x^1부터 x^n까지의 합을 구하는 예제이다.

재귀호출을 사용하여 x^n을 구하는 power( ) 를 작성하였다. x는 2, n은 5로 계산 했기 때문에
2^1 + 2^2 + 2^3 + 2^4 + 2^5 의 결과인 62가 출력 되는 것이다.

class aaa {

    public static void main(String[] args) {

        int x = 2;
        int n = 5;
        long result = 0;

        for(int i = 1; i <= n; i++) {
            result += power(x, i);
        }

        System.out.println(result);

    }

    static long power(int x, int n) {
        if(n==1) {
            return x;
        }
        return x * power(x, n-1);
    }

}