재귀 알고리즘의 정확성 증명

(틀린 부분이 있다면 지적 감사하겠습니다.)

 

우리는 알고리즘을 얼마나 제대로 이해하고 쓸까?

알고리즘을 정확히 이해하고 쓰는것과 그렇지 않은 것에는 많은 차이가 있다. 오늘은 재귀의 예를 소개하고, 그 정확성을 증명해보고자 한다.

 

1. 합 구하기

1부터 x 까지의 합을 구하는 프로그램을 작성해보자.

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

for문을 이용해 1부터 x까지 더했다. 

이번엔 이를 재귀로도 나타내보자.

 

A Simpler Code

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

여기서 나는 재귀를 어떻게 이해했냐면, sum(10)이라고 하면 인자가 10->9->8... 이런식으로 가다가 0이 되고, 0을 리턴하면 다시

쭉~~~ 올라와 1부터 10까지 더해진다고 지금껏 이해했다.

 

sum(3) -> sum(2) -> sum(1) -> sum(0) 

6                   3                 1               0 리턴

 

물론 틀린말은 아니다! 당연한 소리이고, 이런식으로 생각하는 게 이상하지 않다.

그렇지만 이렇게 하나 하나 따라들어가야 된다고??

숫자가 작아서 지금은 문제 없지만 quick sort 의 경우만 보더라도 골치아파지기 시작한다. 또 여러 복잡한 상황이 닥쳐오면 응용력을 잃게 될지도 모른다.

 

위 코드가 1 부터 x까지의 합을 리턴한다는 것을 수학적 귀납법으로 증명해보자.

 

증명 (수학적 귀납법)

P(x) : 함수 sum(x)는 1부터 x까지의 합을 리턴한다. 라고 가정

 

Base 

P(1) 이 참이다 : sum(1)이 리턴하는 값은 1이다.

실제 코드에 1을 대입해보면 1을 리턴함. P(1)은 참이다.

 

Step

P(x-1) -> P(x) 가 참이다. 

"sum(x-1) 이 1+2+....+(x-1) 값을 리턴한다면, sum(x)는 1+2+.....+x 를 리턴한다." 를 증명하면 된다.

 

코드를 보면 sum(x)는 x+sum(x-1)의 값을 리턴한다.

sum(x-1)의 리턴 값은 1+2+....+(x-1)과 같다고 가정했으므로,

sum(x)는 1+2+....+(x-1)+x = 1+2+...+x 을 리턴함을 확인할 수 있음

 

따라서 P(x-1)이 참일 때 P(x)가 참이므로, P는 모든 자연수 x에 대하여 참이다. 

따라서 sum(x)는 1 부터 x까지의 합을 리턴한다.

 

위에서처럼 이해할 때 숫자를 따라 들어가지 않고도, 아주 명쾌하게 증명하였다.

sum(x-1)이 1부터 (x-1) 까지의 합을 리턴한다고 믿었고, 그에 따라 sum(x)가 1부터 x까지의 합을 리턴함을 증명했다.

 

처음보다 더 명쾌하고 쉽게 재귀를 이해할 수 있었다.

이처럼 알고리즘의 정확성을 증명하면 더 알고리즘을 쉽게 이해할 수 있다.