우리는 주로 기존에 있는 알고리즘을 변형하거나 결합하여 새로운 알고리즘을 만들어 낸다. 이는 알고리즘 뿐만 아니라 모든 발명에 해당되는 사항이다. 그렇다면 우리는 기존에 있는 알고리즘의 구조를 이해할 필요가 있다. Induction과 Recursion은 알고리즘의 근간이 되는 기초 개념 중 하나다. 해당 페이지는 중, 고등학교 때 수학 시간에 배웠던 수학적 귀납법과 재귀를 Computer Science 분야로 확장하여 작성하였다.
모든 자연수가 어떤 주어진 성질을 만족시킨다는 명제를 증명하는 방법의 하나이다. 가장 작은 자연수(문맥에 따라 0일 수도 1일 수도 있다)가 그 성질을 만족시킴을 증명한 뒤, 만약 어떤 자연수가 만족시키면 바로 다음 자연수 역시 만족시킴을 증명하기만 하면, 모든 자연수에 대한 증명이 끝난다.
Show that: 모든 자연수 $n$에 대하여 $P(n)$이 참임을 증명하라. (문제)
Base case: 가장 작은 값에 대해 명제가 참임을 증명한다. ($P(0)$ 또는 $P(1)$ 등)
Induction Hypothesis: 임의의 자연수 $k$에 대해 $P(k-1)$가 참이라고 가정한다.
Inductive Step: $P(k)$가 참임을 증명한다.
강한 귀납법(Strong Induction)은 "모든 이전 단계"를 사용하여 다음 단계를 증명하는 방법이다. 따라서 Induction Hypothesis에서 모든 이전 단계에 대해 전부 참이라고 가정한다.
Base case: 가장 작은 값에 대해 명제가 참임을 증명한다.
Induction Hypothesis: 임의의 자연수 $k$에 대해 $P(1),\cdots,P(k-1)$가 모두 참이라고 가정한다.