재귀호출( recursive call)

재귀호출(recursive call) 

- 메서드의 내부에서 메서드 자신을 다시 호출하는 것

- 재귀호출을 하는 메서드를 '재귀 메서드'라 한다. 

 

void method() {
     method();    // 재귀호출. 메서드 자신을 호출한다.
}

 

-> 이 코드 처럼 재귀호출을 계속하면 결국 무한히 자기 자신을 호출하기 때문에 무한 반복에 빠지게 된다. 무한반복 + 조건문 처럼 재귀호출도 조건문이 필수적!!!!

 

void method(int n) {
     if(n==0)
        return;   // n의 값이 0일 때, 메서드를 종료한다.
     System.out.println(n);
     
     method(--n);    // 재귀호출. method(int n)을 호출
}

// 위의 코드와 동일함 
void method(int n { 
    while(n!=0) {
       System.out.println(n--);
     }
}

 

이 코드는 매개변수 n을 1씩 감소시켜가면서 재귀호출을 하다가 n의 값이 0이 되면 재귀호출을 중단하게 된다. 

 

- 반복문대신 재귀호출을 사용하는 이유: 재귀호출이 주는 논리적 간결함 때문! 

-> 어떤 작업을 반복적으로 처리해야 한다면, 먼저 반복문으로 작성해보고 너무 복잡하면 재귀호출로 간단히 할 수 없는지 고민해보기

 

예제) 대표적인 재귀호출의 예인 팩토리얼(factorial)을 구하는 것

5! = 5 * 4 * 3 * 2 * 1 = 120 f(n) = n * f(n-1), 단 f(1) =1

 

public class FactorialTest {

	public static void main(String[] args) {
		int result = factorial(5);   // factorial 메서드의 결과를 result 변수에 삽입
		System.out.println(result);
	}
	static int factorial(int n) {
		int total = 0;   // 초기화
		
		if(n==1)     
			total = 1;
		else 
			total = n * factorial(n-1); // 메서드 자신을 호출
		return total;
	}
}

 

만약 factorial(2)를 호출했을 때의 실행과정

(1) factorial(2)를 호출하면서 매개변수 n에 2가 복사된다. 

(2) 'return 2 * factorial(1)'을 계산하려면 factorial(1)을 호출한 결과가 필요하다. 그래서 factorial(1)이 호출되고 매개변수 n에 1이 복사된다.

(3) if문의 조건식이 참이므로 1을 반환하면서 메서드는 종료된다.  그리고 factorial(1)을 호출한 곳으로 되돌아간다. 

(4)  이제 factorial(1)의 결과값인 1을 얻었으므로, return문이 다음의 과정으로 계산된다.

 return 2 * factorial(1); -> return 2 * 1; -> return 2;

 

값이 점점 커지게 되면 어느 시점에 이르러서는 결국 스택의 저장한계를 넘게 되고, 스택오버플로우 에러(Stack Overflow Error)가 발생한다.

-> 어떤 값이 들어와도 에러없이 처리되는 코드를 작성해야 한다: 매개변수의 유효성검사!!! 

 

static int factorial(int n) {
     if(n <= 0 || n > 12 ) return -1;    //  매개변수 n의 유효성 검사를 추가
     if(n==1) return 1;
     
     return n * factorial(n-1); 
 }

 

매개변수 n의 상한값을 12로 정한 이유는 13!의 값이 메서드 factorial의 반환타입인 int의 최대값(약 20억)보다 크기 때문이다. 만약 그 이상의 값을 구하고 싶으면 반환타입을 int보다 큰 타입으로 변경!(long..) 

 

import java.util.Scanner;
public class FactorialTest {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("숫자를 입력하세요");
		int n = sc.nextInt();
		
		long total = 0;
		
		for(int i=0;i<=n;i++) {
			total = factorial(i);
			
			if(total==-1) {
				System.out.printf("유효하지 않은 값입니다. 다시 입력하세요 (0<n<=20) : %d%n",n);
				break;
			}
			System.out.printf("%2d!=%20d%n",i,total);
		}
	}
	static long factorial(int n) {
		if(n<0 || n>20) return -1;  // 매개변수의 유효성 검사
		if(n<=1) return 1;
		return n * factorial(n-1); 
	}
}

 

이전 예제에 매개변수의 유효성을 검사하는 코드를 추가해서 메서드 factorial의 매개변수 n이 음수이거나 20보다 크면 -1을 반환하도록 했다. 

 

숫자를 입력하세요
21
 1!=                   1
 2!=                   2
 3!=                   6
 4!=                  24
 5!=                 120
 6!=                 720
 7!=                5040
 8!=               40320
 9!=              362880
10!=             3628800
11!=            39916800
12!=           479001600
13!=          6227020800
14!=         87178291200
15!=       1307674368000
16!=      20922789888000
17!=     355687428096000
18!=    6402373705728000
19!=  121645100408832000
20!= 2432902008176640000
유효하지 않은 값입니다. 다시 입력하세요 (0<n<=20) : 21