[Doc.] 재귀 (recursion)

재귀(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!을 구할 수 있음
• 그러나 재귀적 호출이 종료되는 조건이 없다면 무한 호출에 의해 문제가 발생

if (n<=1)

n! = 1

else

n! = n * (n-1)!

↓

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. 하노이의 탑)