재귀호출(recursive call)

재귀함수, 재귀호출

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

 

어떻게 메서드가 자기 자신을 호출할 수 있는가??? 말이 되는 소리인가?

메서드 입장에서는 자기 자신을 호출하는 것과 다른 메서드를 호출하는 것은 차이가 없다고 한다.

'메서드 호출' 이라는 것은 특정 위치에 저장되어 있는 명령들을 수행하는 것이기 때문..

 

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

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

void method(int n) {
	if(n == 0) { // n이 0이라면,
    	return; // 메서드를 리턴함으로 종료시킨다
    }
    System.out.println(n); // n에게 무슨일이 벌어지는지 알기 위한 출력
    method(--n); // 재귀호출
}

 

package 연습문제;
public class recursive01 {
	static void method(int n) {
		if(n==0) {
			return;
		}
		System.out.println("n : " + n);
		method(--n);
	}
	public static void main(String[] args) {
		method(10);
	}
}

 

n : 10
n : 9
n : 8
n : 7
n : 6
n : 5
n : 4
n : 3
n : 2
n : 1

 

매커니즘은 매우 단순한데

왜 응용문제를 보면 이해를 못하겠지..?

 

위의 코드는 아래의 코드와 정확하게 같이 실행된다.

package 연습문제;
public class recursive01 {

	static void method(int n) {
		while(n!=0) {
			System.out.println("n : " + n);
			n--;
		}
	}
    
	public static void main(String[] args) {
		method(10);
	}
}

 

* 반복문은 단순히 같은 문장을 반복해서 수행한다

하지만 메서드를 호출하는 것은 매개변수 복사, 종료 후 복귀할 주소저장 등등.. 이 필요해서 

반복문보다 재귀호출의 수행시간이 더 오래 걸린다..

 

그럼 어째서 반복문대신 재귀호출을 사용하는가?

- > 재귀호출이 주는 논리적 간결함 때문

 

솔직히 반복문이 겹치고 길어지고 겹치고 길어지고 하다보면 보기 힘들다. 일일이 보는게 여간 힘든게 아니다.

반복 작업에 대해 너무 복잡하고 길어진다면 재귀호출을 고민해볼 필요가 있다.

단, 재귀호출은 수행시간이 오래 걸리는 등 비효율적이기 때문에 '간결함'에 대해 급부가 높을 경우에만 사용하자!

 

Factorial을 재귀함수로 구현하기

package 연습문제;
public class recursive01 {
	public static void main(String[] args) {
		
		System.out.println("result : " + factorial(5));
	}
	
	static int factorial(int n) {
		int result = 0;
		
		if(n==1) {
			result = 1; // 무한반복 방지
		} else {
			result = n*factorial(n-1); // 재귀호출
		} // if 끝
		System.out.println("n : " + n + ", result : " + result);
		return result;
	}
}

 

출력물

n : 1, result : 1
n : 2, result : 2
n : 3, result : 6
n : 4, result : 24
n : 5, result : 120
result : 120

 

factorial 메서드를 조금 더 간결하게 적으면,

static int factorial(int n) {
	if(n==1) {
    	return 1;
    }
    return n*factorial(n-1); // 재귀호출
}

이렇게 된다.

 

원리

1. factorial(5)를 호출하며 매개변수 n = 5 복사

2. 'return n * factorial(n-1)'을 계산하려면 factorial(5-1=4)을 호출한 결과가 필요함. 따라서 factorial(4)을 호출한 결과가 필요함

3. 그래서 factoral(4)가 호출되고, factorial(3), factorial(2), factorial(1)이 계속 호출된다.

 - > factorial(4) { return 4*factorial(3) }, factorial(3) {return 3*factorial(2)}, factorial(2) {return 2*factorial(1)}

4. factorial(1)에서 if문이 참이 되니까 1을 리턴하고 메서드가 종료된다. 그리고 factorial(1)을 호출한 곳으로 되돌아간다.

5. factorial(1)의 리턴값 1을 가지고 factorial(2) - > factorial(3) - > factorial(4) - > factorial(5)의 형태로 재귀하여 올라간다

 - > return 1

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

 - > return 3 * factorial(2) (2)

 - > return 4 * factorial(3) (6)

 - > return 5 * factorial(4) (24) = 120

 

만약 factorial 메서드의 매개변수 n의 값이 0(가령, int의 초기화값)이면.. 혹은 10,000와 같이 재귀함수로 감당하기 힘든 값이 인자로 들어가면.. 어덯게 될까?

0이 들어갈 경우 if문의 조건식이 참이 될 수 없다. 따라서 계속해서 재귀호출이 중첩되고 스택의 형태로 데이터가 쌓여만간다.

따라서 어느 시점에서 스택의 저장한계를 넘게되어 자바 내부적으로 예외를 발생시킨다.(StackOverFlow)

 

그래서 재귀함수의 알고리즘에선 '어떤 값이 들어와도 예외없이 처리되는 견고한 코드', 즉 '매개변수의 유효성검사'가 매우 중요함.

static int factorial(int n) {
	if(n <=0 || n >12) { // 유효성 검사를 위해 if문에 조건을 추가해줌
    // n > 12인 이유는 12!이 int의 최대값보다 크기 때문(약 20억)
    	return -1;
    }
    return n * factorial(n-1);
}

 

 

예제2

package 연습문제;
public class recursive02 {

	public static void main(String[] args) {
		int n = 10;
		long result = 0;
		
		for(int i=1; i<=n; i++) {
			result = factorial(i);
			
			if(result == -1) {
				System.out.print("요휴하지 않아요.");
				break;
			} // if 끝
			System.out.printf("%2d!=%20d%n",i,result);
		} // for문 끝
		
	} // main 끝
	
	static long factorial(int n) {
		if(n <= 0 || n > 20) { // Long의 max값보다 크면 안됨(stackOverflow) 1~19
			return -1;
		}
		if(n == 1) { // 1! = 1
			return 1;
		}
		return n * factorial(n-1);
	}
}

 

결과

 1!=                   1
 2!=                   2
 3!=                   6
 4!=                  24
 5!=                 120
 6!=                 720
 7!=                5040
 8!=               40320
 9!=              362880
10!=             3628800

 

* 형식화된 출력, printf()