수학적 귀납법과 재귀

수학적 귀납법과 재귀는 서로 비슷한 구석이 많은 놈들입니다. 원래의 문제를 해결하기 위해 자신의 부분 문제의 해를 이용한다는 점에서 매우 유사하지요... 그러나, 실제 문제가 해결되는 과정을 보면 개념적으로 많이 다릅니다.

수학적 귀납법은 너무나 자명한 기본 상태부터 시작합니다. 그리고 임의의 k에 대해서 증명하고자 하는 명제가 무조건 참임을 가정합니다. 그리고 기본 상태와 k에 대한 무조건적인 가정을 토대로 k+1에 대해 주어진 명제가 참임을 증명하지요.. 그것이 증명된다면 전체 문제에 대해 그 명제가 참임이 자연스럽게 증명되는 방식입니다.

재귀도 이와 비슷합니다. 그러나, 방향이 다릅니다. 수학적 귀납법은 작은 것에서 큰 것으로 나아가는 반면, 재귀는 큰 것에서 작은 것으로 나아가지요. 즉, 하향식 접근 방법을 씁니다. 당연히 수학적 귀납법은 상향식 접근 방법이고요.

자~ 그럼, 예시를 한번 들어볼까요?

동일한 크기의 n개의 도미노가 동일한 간격(그 간격은 도미노의 높이보다는 크지 않아야 합니다.)으로 일렬로 세워져 있습니다.

첫 번째 도미노를 쓰러뜨리면 전체 도미노가 정말 모두 쓰러질까요? 증명해보겠습니다.

출처: scienceall.com

 

수학적 귀납법

1. 초기 상태 : 1번째 도미노는 쓰러진다. (너무 자명합니다. 사람이 직접 쓰러뜨리고 있으니까요..)
2. 귀납 가정 : k번째 도미노가 쓰러진다. (무조건 참이라고 가정합니다.)
3. 귀납 단계 : k번째 도미노가 쓰러지면, 동일한 간격으로 동일한 크기의 도미노이므로 k+1번째 도미노는 쓰러 질 겁니다. (귀납 가정을 토대로 k+1번째에 대해서 참임을 증명했네요..)
그러므로, 모든 도미노는 쓰러진다!!입니다.

재귀

전체 도미노가 쓰러짐을 증명해야 합니다. 자~ 그렇다면 n번째부터 시작해 볼까요? 문제를 점점 작게 만들어 보겠습니다.

1. 전체 도미노가 쓰러짐을 증명하기 위해서는 n번째 도미노가 쓰러짐을 증명해야 합니다.
2. n번째 도미노가 쓰러짐을 증명하기 위해서는 n-1번째 도미노가 쓰러짐을 증명해야 합니다.
3. n-1번째 도미노가 쓰러짐을 증명하기 위해서는 n-2번째 도미노가 쓰러짐을 증명해야 합니다.
4. ......
5. 3번째 도미노가 쓰러짐을 증명하기 위해서는 2번째 도미노가 쓰러짐을 증명해야 합니다.
6. 2번째 도미노가 쓰러짐을 증명하기 위해서는 1번째 도미노가 쓰러짐을 증명해야 합니다.
7. 그런데, 여기서 1번째 도미노는 사람이 직접 쓰러뜨리므로 쓰러집니다.(너무 자명하지요)

이때, 1번째 도미노가 쓰러짐이 증명되면서 2번째 도미노가 쓰러짐이 증명되고, 3번째 도미노가 쓰러짐이 증명되고.... n-1번째 도미노가 쓰러짐이 증명되면서, 마지막으로 n번째 도미노까지 쓰러짐이 증명됩니다.

이제 모든 도미노가 쓰러짐이 증명된 셈이네요! 너무나 자명한 명제(1번째 도미노가 쓰러진다)에 도달하자마자 갑자기 역으로 거슬러가면서 연쇄적으로 증명됩니다.

이렇듯, 수학적 귀납법과 재귀는 본질은 비슷하지만, 문제를 해결하는 방향이 서로 다르지요..

관련 : http://navercast.naver.com/contents.nhn?rid=22&contents_id=2354 (네이버 캐스트 ‘수학 산책’)