[알고리즘 C언어] 3.1 탈출 조건

재귀 알고리즘으로 문제를 해결할 때 주의해야 할 점은 탈출 조건입니다. 재귀 알고리즘으로 문제를 해결할 때는 재귀 호출을 수행하기 이전보다 탈출 조건에 근접하다는 것을 증명할 수 있어야 합니다. 만약 이를 증명하지 못하면 영원히 문제를 해결하지 못할 수 있습니다.

예를 들어 n!를 구하는 알고리즘을 f(n)이라고 할 때 n이 0 이하일 때는 오류를 반환하고 1일 때는 1을 반환하게 해야 합니다. 이와 같이 하면 재귀 호출하기 전보다 n 값이 1이 줄어들어 탈출 조건에 근접합니다. 만약 탈출 조건을 작성하지 않으면 무한 재귀로 스택 오버 플로우가 발생합니다.

Factorial(n)

조건 n<=0    오류

조건 n IsEqual 1   1 반환

반환 n * Factorial(n-1)

이를 코드로 표현하면 다음과 같습니다.

int Factorial(int n)
{
    if(n<0)
    {
        return 0;
    }
    if(n==1)
    {
        return 1;
    }
    return n*Factorial(n-1);
}