[자바 Do It! 알고리즘]Chapter05 재귀 알고리즘 (팩토리얼 구하기)

[재귀]

1. 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 합니다.

※ 1은 자연수입니다. 자연수 n의 바로 다음 수도 자연수입니다.

재귀적 정의(recursive definition)에 의해 무한으로 존재하는 자연수를 위의 두 문장으로 정의할 수 있습니다.

​

[음이 아닌 정수의 팩토리얼(factorial)을 구하는 프로그램]

1. 음이 아닌 정수 n의 팩토리얼(n!) 아래처럼 재귀적으로 정의할 수 있습니다.

0! = 1

n > 0 이면 n! = n x (n-1)!

factorial 메서드를 사용해 3의 팩토리얼 값을 구체적으로 구하는 과정

1. 메서드 호출식 factorial(3)을 실행하면 factorial 메서드가 시작됩니다. 이 메서드는 매개변수 n에 3을 전달받아 3 * factorial(2)를 반환합니다. 그런데 이 곱셈을 수행하려면 factorial(2)의 값을 구해야 합니다. 2를 다시 매개변수로 전달하고 factorial 메서드를 호출합니다.

2. 호출된 factorial 메서드는 매개변수 n에 2를 전달받습니다. 다시 곱셈 2* factorial(1)을 수행하기 위해 factorial 메서드를 호출합니다.

3. 다시 호출된 factorial 메서드는 매개변수 n에 1을 전달받습니다. 1 * factorial(0)을 수행하기 위해 factorial 메서드를 호출합니다.

4. 호출된 factorial 메서드는 매개변수 n에 전달받은 값이 0이므로 1을 반환합니다.

5. 반환된 값 1을 전달받은 factorial 메서드는 1 * factorial(0) [1*1] 을 반환합니다.

6. 반환된 값 2를 전달받은 factorial 메서드는 2 * factorial(1) [2*1] 을 반환합니다.

7. 반환된 값 2를 전달받은 factorial 메서드는 3 * factorial(2) [3*2] 을 반환합니다.

​

[직접 재귀와 간접 재귀]

1. factorial 메서드는 그 내부에서 factorial 메서드를 호출합니다. 이처럼 자신과 같은 메서드를 호출하면 직접(direct) 재귀입니다.

2. 간접(indirect) 재귀는 메서드 a가 메서드 b를 호출하고, 다시 메서드 b가 메서드 a를 호출하는 구조로 이루어집니다.