재귀적
- 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 것
- ex. 팩토리얼
int factorial(int n) {
if (n > 0) return n * factorial(n - 1);
else return 1;
}
재귀 호출
- '함수 자신'을 호출한다고 이해하기보다는 '자기 자신과 똑같은 함수'를 호출한다고 이해
- 직접 재귀 : 자신과 같은 함수를 호출
- 간접 재귀 : 함수 a가 함수 b를 호출하고 다시 함수 b가 함수 a를 호출하는 구조
- 유클리드 호제법 : 두 정수의 최대공약수를 재귀적으로 구하는 방법
int gcd(int x, int y) {
if (y == 0) return x;
else return gcd(y, x % y);
}
재귀 알고리즘 분석
/*--- 재귀 함수 recur ---*/
void recur(int n) {
if (n > 0) {
recur(n - 1);
printf("%d\n", n);
recur(n - 2);
}
}
//매개변수 n으로 4를 전달했을 경우
- 하향식 분석
- 가장 위쪽에 위치한 상자의 함수 호출부터 시작해 계단식으로 자세히 조사해 가는 분석 기법
- 아래 그림 안에 recur(1), recur(2)의 호출이 여러 번 있는 걸 보아, 꼭대기부터 분석하면 같은 함수의 호출이 여러 번 나올 수 있으므로 반드시 효율적인 분석법은 아님
