JAVA - 재귀호출이란?(Recursive Call)

Java programming language.

Imagem de capa

Java에서 메서드를 사용하다보면 메서드 내에서 자신의 메서드와 같은 형태의 메서드를 반복적으로 호출하는 경우가 있습니다. 특히, 수학적인 계산을 할 경우에 말이죠.

1. 재귀호출(Recursive Call)이란?


▶ 재귀호출의 예


▶ 팩토리얼의 정규식

f(n) = n * f(n-1)

단, f(1) = 1

5! = 5 × 4 × 3 × 2 × 1 = 120

팩토리얼을 자바코드로 구현하면 아래와 같습니다.

public long factorial(int n) {
	long result = 0;

	if (n == 1) {
		result = 1;
	} else {
		result = n * factorial(n - 1);
	}

	return result;
}


위의 코드에서 중요한 로직은

n = 1 이면,
	1 을 리턴하고,
n = 1 이 아니면,
	n * factorial(n-1) 입니다.






그래서 factorial(5)가 호출되면, result = 5 * 4 * 3 * 2 * 1 이 리턴되는 것입니다.


위의 내용을 예제코드와 그림으로 살펴보겠습니다.


▶ 예제코드

Factorial.java

/**
 * @file name : Factorial.java
 * @date : 2013. 8. 15.
 * @discription : 팩토리얼 클래스
 * @author Cremazer(cremazer@gmail.com)
 */
public class Factorial {
	public long factorial(int n) {
		long result = 0;

		if (n == 1) {
			result = 1;
		} else {
			result = n * factorial(n - 1);
		}

		return result;
	}
}


FactorialTest.java

/**
 * @file name : FactorialTest.java
 * @date : 2013. 8. 15.
 * @discription : 팩토리얼 테스트 클래스
 * @author Cremazer(cremazer@gmail.com)
 */
public class FactorialTest {
	public static void main(String[] args) {
		Factorial f = new Factorial();
		int n = 5;
		System.out.println(n + "! = " + f.factorial(n));
	}
}


▶ 결과

5! = 120


펙토리얼을 테스트 하기 위해 main() 메서드에서 Factorial객체 f를 생성하여 f를 이용해 facltorial(int n)에 접근해 봤습니다.

이 과정을 그림으로 살펴보면 아래와 같음을 알 수 있습니다.


▶ 팩토리얼의 호출 원리

그림1. 20180425_001_What-is-a-recursive-call

그림2. 20180425_002_What-is-a-recursive-call

그림3. 20180425_003_What-is-a-recursive-call

그림4. 20180425_004_What-is-a-recursive-call

그림5. 20180425_005_What-is-a-recursive-call

그림6. 20180425_006_What-is-a-recursive-call

그림7. 20180425_007_What-is-a-recursive-call

그림8. 20180425_008_What-is-a-recursive-call

그림9. 20180425_009_What-is-a-recursive-call

그림10. 20180425_010_What-is-a-recursive-call

그림11. 20180425_011_What-is-a-recursive-call

그림12. 20180425_012_What-is-a-recursive-call

그림13. 20180425_013_What-is-a-recursive-call