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

[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);

}