코딩하는 공무원

수학적 귀납법과 재귀는 서로 비슷한 구석이 많은 놈들입니다. 원래의 문제를 해결하기 위해 자신의 부분 문제의 해를 이용한다는 점에서 매우 유사하지요... 그러나, 실제 문제가 해결되는 과정을 보면 개념적으로 많이 다릅니다. 수학적 귀납법은 너무나 자명한 기본 상태부터 시작합니다. 그리고 임의의 k에 대해서 증명하고자 하는 명제가 무조건 참임을 가정합니다. 그리고 기본 상태와 k에 대한 무조건적인 가정을 토대로 k+1에 대해 주어진 명제가 참임을 증명하지요.. 그것이 증명된다면 전체 문제에 대해 그 명제가 참임이 자연스럽게 증명되는 방식입니다. 재귀도 이와 비슷합니다. 그러나, 방향이 다릅니다. 수학적 귀납법은 작은 것에서 큰 것으로 나아가는 반면, 재귀는 큰 것에서 작은 것으로 나아가지요. 즉, 하향식 ..