[디딤돌 자료구조와 알고리즘 with C] 3. 재귀 알고리즘

3. 재귀 알고리즘

 

 이번에는 재귀 알고리즘을 살펴봅시다.

 

 재귀 알고리즘은 문제를 해결하기 위해 자신의 알고리즘을 이용하여 해결하는 것을 말합니다. 수학에서 특정 명제가 참인지 증명하기 위해 명제를 이용하여 증명하는 방법과 같은 방식입니다. 예를 들어 "n!을 f(n)이라 할 때 n>1인 정수이면 n!은 n*f(n-1)이다."라는 명제를 증명하면 다음과 같이 증명할 수 있습니다.

 

 n-1일 때 위 명제가 참이라 가정하자. 가정에 의해 f(n-1) = (n-1)*(n-2)*...*3*2*1 이다.

n*f(n-1) = n*(n-1)*(n-2)*...*3*2*1 = n! 이므로 위 명제는 참인 명제이다.

 

 이처럼 자신을 이용하여 문제를 해결하는 방법을 재귀적 귀납법이라 하는데 이와 같은 방법으로 문제를 해결하는 알고리즘을 재귀 알고리즘이라 부릅니다.

 

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

}