[Java/자바] 재귀호출이란 ?

재귀호출이란 ?

메서드의 내부에서 메서드 자신을 다시 호출하는 것을 말합니다.

그리고 재귀호출을 하는 메서드를 "재귀 메서드"라고 합니다.

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

 

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

무한반복문이 조건문과 함께 사용되어야 하는 것처럼, 재귀호출도 조건문이 필수적으로 따라다닙니다.

void method(int n) {
	if(n==0) return; // n의 값이 0이라면 메서드 종료.
    System.out.println(n);
    
    method(--n); // 재귀호출.
}

 

반복문보다 재귀호출이 더 빠른가 ?

결론부터 말하면 아닙니다.

메서드를 호출하는 것은 반복문보다 몇 가지 과정이 추가로 더 필요하기 때문에 반복문보다 재귀호출의 수행시간이 더 오래 걸립니다. 

 

그럼에도 왜 굳이 재귀호출을 사용할까?라고 생각이 들 수 있습니다.

그 이유는 재귀호출이 주는 간결함 때문입니다.

여러 개의 반복문과 조건문으로 복잡하게 작성된 코드를 재귀호출로 작성하면 보다 단순하고 간결하게 작성할 수 있을 겁니다.

하지만 재귀호출은 비효율적이므로 재귀호출에 드는 비용보다 재귀호출의 간결함이 주는 이득이 충분히 큰 경우에만 사용해야 합니다.

 

---

재귀호출 응용 1 : 재귀호출을 이용해 n팩토리얼 구하기

재귀호출을 이용하여 다음과 같이 n! (팩토리얼)의 값을 구할 수 있습니다.

factorial() 메서드에 매개변수로 5를 준다면

n이 1일때 까지 다음과 같이 실행되고 n이 1이라면 1을 반환하며 다음과 같이 계산하게 됩니다.

5 * 4 * 3 * 2 * 1 = 120

 

class FactorialTest {
	public static void main(String args[]) {
		 // main메서드와 같은 클래스에 있기 때문에 static 메서드를 호출할 때 클래스 이름을 생략 가능하다.
		// FactorialTest.factorial(4)대신 factorial(4)
		System.out.println(factorial(5));
	}

	static long factorial(int n) {  // static 메서드이므로 인스턴스를 생성하지 않고 직접 호출할수 있게 해준다.
		if (n == 1) return 1;		
		else return n * factorial(n-1); //factorial 메서드 재귀호출
	}
}

출력 결과

 

---

재귀호출 응용 2 : x^1 부터 x^n까지의 합 구하기

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; 

		// x = 3, n = 3 일시 : 3 * power(3, 2) * power(3, 1)
		// 즉 3 * 3 * 3
		return x * power(x, n-1);
	} 
}

출력 결과

power 메서드는 int x와 int n을 매개변수로 받아 n이 1일 시 x값을 리턴하고 아니라면 power메서드를 재귀호출합니다.

x가 2이고 n이 5일시, x = 2를 5번곱합니다. ( 2 * 2 * 2 * 2 * 2 )

 

main에서는 for 반복문으로 power메서드를 이용해 2^1부터 ~ 2^5 까지 값을 result 변수에 추가합니다.

 

---

참고자료 : 자바의정석3