🐢 재귀함수 (recursion): 직접 또는 간접적으로 자기 자신을 호출하는 함수이다.
- recursive definition (재귀적 정의) 가능한 문제들을 recursion으로 풀 수 있다.
🐢 recursion vs. iteration
대부분의 재귀는 반복으로 바꿔서 작성할 수 있다.
- recursion
1. 성능이 좋지 않다.
2. 많은 내부 함수 호출로 인해 overhead (함수호출은 context switch overhead 발생)
- iteration
1. 수행속도가 빠르다. (성능이 좋다.)
2. 재귀적인 문제에서는 프로그램 작성이 아주 어려울 수 있다.
🐢 factorial programming (by recursion)
int factorial(int n){
if(n==1) return 1; // stopping condition을 n==1로
else return (n*factorial(n-1)); // 분할 정복 방법
}
🐢 재귀 알고리즘의 구조
! '재귀 호출을 하는 부분'과 '재귀 호출을 멈추는 부분'을 꼭 포함해야한다.
- 재귀 호출을 멈추는 부분 stopping condition이 없다면 시스템 오류가 발생할 때까지 무한정 호출하게 된다.
🐢 factorial programming (by iteration)
int factorialIter(int n){
int result=1;
for(int k=n;k>0;k--) result=result*k;
return result;
}
🐢 재귀적인 방법이 반복적인 방법보다 더 효율적인 (드문) 예
: 숫자 x의 n의 제곱값을 구하는 문제
// 방법1. 반복문 사용
double slow_power(double x, int n){
double r=1.0;
for(int i=0;i<n;i++) r=r*x;
return r;
}
// 방법2. 재귀적인 호출
double power(double x, int n){
if(n==0) return 1;
else if(n%2==0 return power(x*x,n/2); // 짝수인 경우
else return x*power(x*x,(n-1)/2); // 홀수인 경우
}
// 호출 시마다 n이 반씩 줄어든다. --> 시간 복잡도: O(logn)
🐢 재귀 호출을 사용하면 비효율적인 예
: 피보나치 수열
// 방법1. 재귀적인 구현
int fib(int n){
if(n==0) return 0;
if(n==1) return 1;
return fib(n-1)+fib(n-2);
}
// 같은 항이 중복해서 계산된다.
// 방법2. 반복적인 구현
int fibIter(int n){
if(n<2) return n;
else{
int i, tmp, current=1, last=0;
for(int=2;i<n;i++){
tmp=current;
current+=last;
last=tmp;
}
return current;
}
}
🐢 iteration으로 바꾸기 어려운 경우 (즉, recursion이 더 적절한 경우)
- 하노이탑처럼 여러 곳에서 자신을 호출하는 경우
- 꼬리 순환 vs. 머리 순환
--> 꼬리 순환이 iteration으로 변환하기 쉽다.
return n*fact(n-1); // 꼬리 순환
return fact(n-1)*n; // 머리 순환
🐢 영역채색
- 다중 재귀: 한 번의 호출이 발생할 때마다 2개 이상의 재귀 호출이 이뤄지는 경우
- 선형 재귀 (1개 호출)
ex) factorial, 거듭제곱
- 이진 재귀 (2개 호출)
ex) 피보나치 수열, 하노이 탑
! 재귀 함수 호출이 증가할수록 perfomance는 떨어진다.