6-3 메소드의 재귀호출

자바는 메소드의 재귀호출을 지원합니다. 이 내용이 어렵다면 눈으로 쭉 보고 넘긴 후에 나중에 다시 보셔도 됩니다.

 

메소드의 재귀는 자료구조나 알고리즘 등에서 많이 유용하게 사용되고 있습니다.

 

재귀는 고등학교 수학시간에 배우는 팩토리얼(factorial)의 개념과 같습니다.

 

public class ReculFactorial {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println("3 factorial : " + factorial(3));
		System.out.println("12 factorial : " + factorial(12));
	}
	
	public static int factorial(int n) {
		if(n==1)
			return 1;
		else
			return n*factorial(n-1);
	}

}

n이 1이면 1, 만약에 n이 5라면

 

5! = 5 * 4 * 3 * 2* 1 과 같은 연산이 이루어집니다.

 

아직 실행이 완료되지 않은 메소드를 어떻게 다시 호출할 수 있냐면, 메모리에 저장된 메소드를 구성하는 명령문이 CPU로 이동해서 실행이 되기 때문입니다.

 

따라서 메소드를 구성하는 명령문은 얼마든지 CPU로 이동해서 실행이 가능하기 때문에 기존에 호출된 메소드가 완료되지 않았다고 해서 호출이 불가능한 것은 아닙니다. 메소드의 앞 부분을 구성하는 명령문만 반복해서 CPU로 이동시킬 수 있기 때문입니다.

 

public class InfRecul {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		showHi(3);
	}

	public static void showHi(int cnt) {
		System.out.println("Hi~ ");
		showHi(cnt--);
		if(cnt==1)
			return;
	}
}

이번엔 잘못된 재귀 메소드를 보겠습니다.

 

위 예제는 showHi 메소드가 재귀의 고리를 끊을 수 없습니다. 이유는 if(cnt==1)의 조건을 만족할 수 없기 때문입니다.

 

한 줄 위에 cnt-- 를 보면 cnt 변수 뒤에 -- 연산자가 붙었기 때문에 메소드 호출을 통해 인자가 전달되고 난 다음에야 cnt의 값이 하나 감소합니다. 따라서 5행에서 전달된 값 3은 줄지 않고 계속해서 매개변수의 초기화 값으로 사용이 됩니다. 따라서 올바르게 고쳐보면 cnt--를 --cnt로 고쳐야합니다. 그리고 showHi(cnt--); 의 위치도 바꿔야 합니다.

 

옳게 바꾸면 이렇습니다.

 

public class RightRecul {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		showHi(3);
	}

	public static void showHi(int cnt) {
		System.out.println("Hi~ ");
		if(cnt==1)
			return;
		showHi(--cnt);
	}

}

재귀 메소드 정의의 주의사항 두가지는 이렇습니다.

-재귀의 연결 고리를 끊기 위한 조건검사의 위치가 적절해야한다.

-재귀의 연결 고리를 끓기 위한 조건검사ㅑ가 true가 되도록 적절한 연산이 이뤄져야한다.

 

재귀 메소드는 메소드의 빈번한 호출로 인해 문제가 있을 수 있습니다. 과도한 메모리 사용으로 인해서 성능의 저하가 이어지기 때문입니다. 그러나 이러한 문제에도 재귀 메소드가 쓰이는 이유는

 

-복잡한 문제를 간결하게 해결할 수 있다.

-수백 줄 이상의 코드가 요구되는 문제를 수십줄의 코드로 해결할 수 있다.

 

라는 두가지 장점이 있기 때문에 자료구조와 알고리즘에서 중요한 위치를 차지하고 있습니다.