[JAVA] 재귀 호출(recursive call)

재귀호출(recursive) 

- 메서드 내에서 자기자신을 반복적으로 호출하는 것

- 재귀호출은 반복문으로 바꿀 수 있으며 반복문보다 성능이 나쁨

- 이해하기 쉽고 간결한 코드를 작성할 수 있다

 

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

 

 

호출된 메서드는 '값에 의한 호출(call by value)' 을 통해, 원래의 값이 아닌 복사된 값으로 작업하기 때문에 

호출한 메서드와 관계없이 독립적인 작업 수행이 가능하다. 

 

그런데 위처럼 오로지 재귀호출뿐이면, 무한히 자기 자신을 호출하기 때문에 무한 반복에 빠지게 된다. 

무한 반복문이 조건문과 함께 사용해야하는 것처럼 재귀호출도 조건문이 같이 나와야한다. 

 

 

 

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

반복문으로도 작성 가능하다. 

 

 

 

 

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

 

 

예15) //팩토리얼

public class FactorialTest {
	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;
	}
}

 

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

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

그래서 FactorialTest.factorial(4) 대신 factorial(4)로 했다.

 

 

매개변수의 유효성 검사

static int factorial(int n){
	if(n<=0 || n>12) return -1;
	if(n==1) return 1;

	return n*factorial(n-1);
}

매개변수 n의 상한값을 12로 정한 이유는 13!의 값이 메서드factorial의 반환타입인 int보다 크기 때문이다. 

만일 그 이상의 값을 구하고 싶으면 반환 타입을 int보다 큰 타입으로 변경하면 된다.

 

 

예16)

public class FactorialTest2 {
	static long factorial(int n) {
		if (n <= 0 || n > 20)
			return -1;
		if (n <= 1)
			return 1;
		return n * factorial(n - 1);
	}

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

		for (int i = 1; i <= n; i++) {
			result = factorial(i);

			if (result == -1) {
				System.out.printf("유효하지 않은 값입니다. (0<n<=20): %d%n", n);
				break;
			}
			System.out.printf("%2d! = %20d%n", i, result);
		}
	}

}

 

 

예17) //무한 호출

public class MainTest {
	public static void main(String[] args) {
		main(null); //재귀호출, 자기 자신을 다시 호출한다.
	}
}

 

main메서드가 종료되지 않고 호출스택에 쌓여서 호출스택의 메모리 한계를 넘게되고 StackOverflowError 가 발생.

 

 

 

예18)

public class PowerTest {
	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;
		else
			return 
					x * power(x, n - 1);
	}
}

 

x^1부터 x^n까지 합을 구한다. 

재귀호출을 사용하여 x^n을 구하는 power()를 작성했다. 

x는 2, n은 5로 계산했기 때문에 2^1+2^2+2^3+2^4+2^5 의 결과인 62가 출력되었다. 

 

f(x,n) =x* f(x, n-1), 단 f(x, 1) = x