[Java] 객체지향 프로그래밍(oop) - 재귀호출(recursive call)

📖재귀호출

재귀호출이란?

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

• 재귀호출은 반복문으로 바꿀 수 있으며 반복문보다는 성능이 나쁘다.

• 이해하기 쉽고 간결한 코드를 작성할 수 있다는 장점이 있다.

• 재귀호출 예시 : 팩토리얼, 제곱, 트리운행, 폴더목록 표시...

🤔 팩토리얼이란?

• 팩토리얼 : 한 정수를 1이 될 때까지 1씩 감소시켜가면서 곱해나가는 것
  • 4팩토리얼 : 4 * 3 * 2 * 1
  • 함수 : f(n) = n * f(n-1) 단, f(1) = 1

long factorial(int n) {
	long result = 0;
	if(n==1) {
		result = 1;
	} else {
		result = n * factorial(n-1);
	}
	return result;
}

하나의 정수를 매개변수로 입력받아서 n이 1일 때는 1을 반환하고,
1이 아닐 때는 메서드 자기자신을 다시 호출한다.

팩토리얼 메서드의 실행과정

1. FactorialTest클래스가 메모리에 로드되고, FactorialTest클래스의 main메서드가 호출되면서 프로그램이 시작된다.

2. long타입의 변수 result가 main메서드의 지역변수로 생성된다. factorial메서드를 호출하면서 매개변수로 4를 넘겨준다.

3. n * factorial(n-1)을 수행하는 과정에서 다시 factorial메서드가 호출된다. 매개변수로는 n-1, 현재 n의 값이 4이므로 3이 넘겨진다. n이 1이 될 때까지 이 과정을 반복한다.

4. n==1이면 지역변수 (if문에 의해서 result = 1)result의 값 1을 자신을 호출한 메서드에게 반환하면서 수행중인 메서드는 종료된다.

5. factorial메서드를 호출했던 곳으로 돌아가서 다시 수행을 계속한다. factorial(n-1)대신 factorial(n-1)을 호출한 결과로 반환받은 값 1이 사용되어 계산된다.

6. 지역변수 result의 값 2를 자신을 호출한 메서드에게 반환하면서 현재 수행중인 메서드는 종료된다. main메서드에서 factorial메서드를 처음 호출한 곳으로 돌아갈 때까지 이 과정이 반복된다.

7. factorial메서드의 수행결과로 반환받은 값 24가 main메서드의 지역변수 result에 저장된다.

8. println메서드를 호출해서 result의 값을 출력한다. println메서드가 종료되어 호출스택에서 제거되고 main메서드로 돌아간다. main메서드도 더 이상 진행할 문장이 없으므로 호출스택에서 제거되고 프로그램은 종료된다.