어떤 때 쓰냐면, 어떤 답을 구하기 위해서 일련의 숫자만 다른 똑같은 과정을 반복할 때 쓴다. 가령 어떤 자연수 n의 팩토리얼을 구하기 위해서는
$$ f(n) =
\begin{cases}
n \times f(n-1) & \mbox{if } n \ge 1 \\
1 & \mbox{if } n = 0
\end{cases}
$$
와 같이 구해야 한다. 이를 C 코드로 쓰면 다음과 같이 된다.
1
2
3
4
5
6
|
int factorial(int n){
if(n==0)
return 1;
else
return n*factorial(n-1);
}
| cs |
재귀함수를 사용해서 쉽게 풀 수 있는 문제가 있고, 절대 재귀함수를 쓰면 안 되는 문제가 있는데, 전자의 예시는 하노이 탑 문제고 후자의 예시는 피보나치 수 구하기이다. 왜 후자에 재귀함수를 쓰면 안 되는지부터 말해보자면, 7번째 피보나치 수를 구하는 데에만 25번의 연산이 필요하기 때문이다. 10000번째 피보나치 수를 구하는 코드를 재귀로 짜서 돌린다면 하루 종일이 걸려도 모자랄 수 있다...
하지만 하노이 탑 문제는 재귀로 짜면 아주 짧은 코드로 간단하게 해결할 수 있다. 하노이 탑 문제를 C 코드로 짤 수 있다면 재귀가 대충 뭔지를 이해했다고 본다고 하더라.
막대 A, B, C가 있고 A에 있는 n개의 원반을 C로 옮기는 문제는 다음과 같이 푼다.
1. 원반 n-1개(맨 아래 원반 제외) A에서 B로 이동
2. n번째(맨 아래, n개 중 가장 큰 원반) A에서 C로 이동
3. 1에서 옮긴 n-1개 원반을 B에서 C로 이동
C 코드로 쓰면 다음과 같다.
1
2
3
4
5
6
7
8
9
|
int HanoiTower(int n, char a, char b, char c){
if(n==1)
printf("원반 %d : a to c", n);
else{
HanoiTower(n-1, a, c, b);
printf("원반 %d : a to c", n);
HanoiTower(n=1, b, a, c);
}
}
| cs |
댓글 없음:
댓글 쓰기