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

6. 재귀 알고리즘

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

 

재귀 알고리즘은 문제를 해결하기 위해 자신의 알고리즘을 이용해서 해결하는 알고리즘입니다. 수학에서 명제가 참인지 거짓인지 증명하기 위해 명제를 이용해서 증명하는 방법과 같은 방식입니다.

 

예를 들어 "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