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

a 반환된 값 2를 전달받은 factorial 함수는 3 * factorial(2)(3 * 2)를 반환합니다.

이렇게 하면 factorial(3)을 사용해 순차곱셈의 값 6을 얻을 수 있습니다. factorial 함수는 n - 1
의 순차곱셈 값을 구하기 위해 다시 factorial 함수를 호출합니다. 이러한 함수 호출 방식을 재귀
호출(recursive call)이라고 합니다.

재귀 호출은 ‘함수 자신’을 호출한다고 이해하기보다는 ‘자기 자신과 똑같은 함수’를 호출한다고 이해하는 것이 자연스럽
습니다. 만약 진짜로 함수 자신을 호출하면 끝없이 자기 자신을 호출하는 행위를 계속할 테니까요.

직접 재귀와 간접 재귀
factorial 함수는 그 내부에서 factorial 함수를 호출합니다. 이처럼 자신과 같은 함수를 호출
하면 직접(direct) 재귀입니다(그림 5-3 a ). 간접 재귀(indirect)는 함수 a가 함수 b를 호출하고,

다시 함수 b가 함수 a를 호출하는 구조로 이루어집니다(그림 5-3 b ).

a 직접 재귀 b 간접 재귀
함수 a 함수 a
함수 b
a(); b();
a();
함수 b
함수 a
a();
b();

자기 자신과 같은 함수가 호출됩니다. 다른 함수를 통해 자기 자신과 같은 함수가 호출됩니다.
[그림 5-3] 직접 재귀와 간접 재귀

재귀 알고리즘에 알맞은 경우는 ‘풀어야 할 문제’, ‘계산할 함수’, ‘처리할 데이터 구조’가 재귀
로 정의되는 경우입니다. 앞에서 살펴본 ‘순차곱셈 값을 구하는 예’는 많은 재귀 알고리즘의

사용 방법 가운데 하나입니다.

유클리드 호제법

두 정수의 최대공약수(greatest common divisor)를 재귀적으로 구하는 방법을 알아보겠습니
다. 두 정수를 직사각형의 두 변의 길이라고 생각하면 두 정수의 최대공약수를 구하는 문제는

아래 문제처럼 바꿀 수 있습니다.

직사각형을 정사각형으로 완전히 채웁니다. 이렇게 만들 수 있는 정사각형의 가장 긴 변의 길이를 구하세요.

168 C 알고리즘