Page 167 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

재귀 호출

factorial 함수를 사용해 3의 순차곱셈 값을 구체적으로 구하는 과정을 그림 5-2를 통해 살펴
보겠습니다.

a 함수 호출식 factorial(3)을 실행하면 factorial 함수가 시작됩니다. 이 함수는 매개변수 n

에 3을 전달받아 3 * factorial(2)를 반환합니다. 그런데 이 곱셈을 수행하려면 factorial(2)의
값을 구해야 합니다. 2를 다시 매개변수로 전달하고 factorial 함수를 호출합니다.

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

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

d 호출된 factorial 함수는 매개변수 n에 전달받은 값이 0이므로 1을 반환합니다.
d 에서 처음으로 return문이 실행됩니다.

인수
factorial( 3 );
반환값
3
a int factorial(int n) {
if(n > 0) 6
return n * factorial(n - 1);
else 2
return 1;
b int factorial(int n) {
}
if(n > 0) 2
return n * factorial(n - 1);
else 1
return 1;
c int factorial(int n) {
}
if(n > 0) 1
return n * factorial(n - 1);
else 0
d return 1;
int factorial(int n) {
}
if(n > 0)
return n * factorial(n - 1);
else 1
return 1;
}
[그림 5-2] 3의 순차곱셈 값을 재귀적으로 구하는 과정

c 반환된 값 1을 전달받은 factorial 함수는 1 * factorial(0)(1 * 1)을 반환합니다.
b 반환된 값 1을 전달받은 factorial 함수는 2 * factorial(1)(2 * 1)을 반환합니다.

05•재귀 알고리즘 167