이번에는 재귀 알고리즘을 살펴봅시다.
재귀 알고리즘은 문제를 해결하기 위해 자신의 알고리즘을 이용해서 해결하는 알고리즘입니다. 수학에서 명제가 참인지 거짓인지 증명하기 위해 명제를 이용해서 증명하는 방법과 같은 방식입니다.
예를 들어 “n! 을 f(n)이라고 할 때 f(1)=1이고 n>1인 정수이면 f(n)=n*f(n-1)이다.”라는 명제를 증명하면 다음처럼 증명할 수 있습니다.
n-1일 때 위 명제가 참이라고 가정합시다.
가정에 의해 f(n-1) = (n-1)*(n-2)*(n-3)*…*3*2*1입니다.
f(n) = n*(n-1)*(n-2)*(n-3)*…*3*2*1 = n*f(n-1) 이므로 위 명제는 참인 명제입니다.
이처럼 명제 자신을 이용하여 명제를 증명하는 것을 재귀적 귀납법이라고 부르는데 이러한 방법으로 문제를 해결하는 알고리즘을 재귀 알고리즘이라고 부릅니다.
재귀 알고리즘으로 문제를 해결할 때 주의할 점은 탈출 조건입니다. 재귀 알고리즘으로 문제를 해결할 때는 재귀 호출을 수행하기 이전보다 탈출 조건에 근접하다는 것을 증명할 수 있어야 합니다. 만약 이를 증명하지 못하면 영원히 문제를 해결하지 못할 수 있습니다.
“재귀 알고리즘으로 문제를 해결할 때 주의할 점은 탈출 조건입니다.”
예를 들어 n!를 구하는 알고리즘을 f(n)이라고 할 때 n이 0 이하일 때는 오류를 반환하고 1일 때는 1을 반환하게 해야 합니다. 이와 같이 하면 재귀 호출하기 전보다 n 값이 1이 줄어들어 탈출 조건에 근접합니다. 만약 탈출 조건을 작성하지 않으면 무한 재귀로 스택 오버 플로우가 발생합니다.
Factorial(n)
조건 n<=0 오류
조건 n IsEqual 1 1 반환
반환 n * Factorial(n-1)
이를 코드로 표현하면 다음과 같습니다.
#include <iostream>
using namespace std;
long long Factorial(int n)
{
if(n<0)
{
return 0;
}
if(n==1)
{
return 1;
}
return n*Factorial(n-1);
}
int main()
{
for(int i = 0; i<=10;i++)
{
cout<<i<<"!="<<Factorial(i)<<endl;
}
return 0;
}
▷ 실행 결과
0!=0 1!=1 2!=2 3!=6 4!=24 5!=120 6!=720 7!=5040 8!=40320 9!=362880 10!=3628800