수학적 귀납법으로 재귀 알고리즘 증명

수학적 귀납법으로 재귀 알고리즘을 증명하기 위해선 다음의 두 가지만 확인하면 된다.

① P(1) 이 참이다.

② P(x-1) -> P(x) 는 참이다.

즉, P(x-1) 이 참이라고 믿고(가정) P(x) 확인! :: 재귀 코드는 "재귀는 항상 성공한다"고 읽으면 됨

 

다음의 두 코드를 살펴보자. (c언어로 작성되었습니다.)

int sum(int x)
{
    int i, num;
    num=0;
    for (int i=0; i<num; i++)
    	num+=i;
    return num;
}

int sum2(int x){
	if(x<=0) return 0;
    else return x+ sum(x-1);
}

두 코드는 모두 1부터 인자로 받은 x 까지의 합을 반환하는 함수이다.

단, 위의 코드는 반복적 절차(iterative process) 로, 아래의 코드는 재귀적 절차(recursive process) 로 작성되었다.

이 때, 이 두 코드가 정말 '1부터 x 까지의 합을 리턴' 한다는 것을 증명할 수 있는가?

 

반복적 절차인 위의 코드는 '하나씩' 설명할 수 있다.

하지만 재귀 코드는 하나씩, ~로 들어가서 등의 방식으로는 짐작해서 이해하기 힘들다.

이럴 때 수학적 귀납법을 통해 명쾌하고 간단하게 증명할 수 있다.

 

<Proof> P(n) : sum(x) 는 1+2+...+x 를 (항상) 리턴한다.

1. (Base) P(1) 이 참이다 : sum(1) 이 리턴하는 값은 1 이다 -> 코드에 1을 대입하면 1을 리턴함을 알 수 있음

2. (Step) P(x-1) -> P(x) 이 참이다 : sum(x-1) 이 1+2+...+(x-1) 을 리턴하면 sum(x) 는 1+2+...+(x-1)+x 를 리턴한다.

=> 코드를 보면 sum(x) 는 x + sum(x-1) 의 값을 리턴한다. sum(x-1) 은 1+2+...+(x-1) 과 같다고 가정했으므로 sum(x) 는 x + (1+2+...+x-1) 을 리턴함을 확인할 수 있다.

 

다시 말해, sum(x-1) 이 "자신의 역할을 한다" , "재귀가 성공한다" 라고 '믿는다'면, sum(x) 는 그 믿는 가정에서 sum(x) 가 되어야 하는 것을 함께 리턴하기 때문에 참임을 증명할 수 있는 것이다.

 

이렇듯, 수학적 귀납법으로 재귀를 간단하게 증명할 수 있으니 수학적 귀납법이 증명에 유용함을 알 수 있다.

 

이 재귀 코드의 Complexity 를 살펴보자.

T(n) = 1 + T(n-1)

      = 1+ 1 + T(n-2) = .... = n

∴ T(n) = O(n)

n 하고 비슷한 시간이 걸림을 알 수 있다.

복잡도는 조금 다르지만, 위의 반복적 절차 코드 역시 n 번 반복하게 되므로 n 시간이 걸리게 된다.