재귀(Recursion)
수학이나 컴퓨터 과학 등에서 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다. 주로 이 방법은 함수에 적용한 재귀 함수(Recursion Function)의 형태로 많이 사용된다.
- Wiki, 위키 백과 -
특징
- 구현하려는 알고리즘 자체가 재귀적 특성을 갖는다면, 재귀 함수를 이용하면 쉽게 구현이 가능하다.
- 프로그램 내의 반복문은 재귀호출로 바꿀 수 있으며, 그 반대로 재귀호출은 반복문으로 고쳐 쓸 수 있다.
- 일반적으로 재귀 함수는 반복문을 이용한 함수로 변환이 가능
long factorial(int number)
{
...
factorial(number - 1); // 함수 내부에서 자기 자신의 함수를 호출 (재귀함수)
...
}
n!
- 수식 n! (n factorial)은 1 * 2 * 3 * ... * (n-2) * (n-1) * n 을 의미
계승 수식은 재귀적 특성을 갖음
- 즉 n!을 구하기 위해서 (n-1)!을 먼저 구한다면 쉽게 n!을 구할 수 있음
- 그러나 재귀적 호출이 종료되는 조건이 없다면 무한 호출에 의해 문제가 발생
↓
long factorial(int number)
{
if (number <= 1)
return 1;
else
return (number * fatorial (number -1));
}
피보나치 수
- 다음 수가 앞의 두 수의 합이 되는 수열
0 1 1 2 3 5 8 13 21 ...
- n번째 수를 Fn이라 하면, Fn은 다음과 같이 재귀적으로 표현
- 피초나치 수를 발생시키는 프로그램을 작성한다면 재귀적 특성을 이용하여 쉽게 구현 가능.
int fibo(int n)
{
if (n==0) return 0;
else if (n==1) return 1;
else return return fibo(n-1) + fibo(n-2);
}
main()
{
printf("%d", fibo(4));
}
- 반복적 방법을 이용하여 구현
long fibo (int n)
{
int fn, fn1, fn2;
int i;
if (n <=1) return n;
else {
fn2 = 0;
fn1 = 1;
for (i=2; i<=n; i++) {
fn = fn1 + fn2;
fn2 = fn1;
fn1 = fn;
}
return fn;
}
}
팩토리얼 문제나 피보나치 수열 문제 말고도 재귀를 대표하는 문제들을 많이 있습니다. (ex. 하노이의 탑)
'알고리즘 > 재귀' 카테고리의 다른 글
| [재귀] 계단 오르기 (0) | 2014.05.15 |
|---|---|
| [재귀] 유클리드 호제법 (0) | 2014.05.15 |
| [재귀] x의 y 거듭제곱 (0) | 2014.05.15 |
