再帰と帰納法

帰納法の考え方
最初の一歩と次の一歩を分けて考える
言わば、「棚上げ」の構造
いきなり全部は無理、だから一歩ずつやってみよう
例: n 個の数の和を求める
いきなり n 個は無理
a_0 〜 a_{k-2} まで足せたとして a_{k-1} をどうするか考える
sum(a,k) = sum(a,k-1) + a_{k-1} という再帰的定義の発想
後は n が 0 の場合を考えればよい
sum(a,0) = 0
再帰的定義
sum(a,k) = if k == 0 then 0 else sum(a,k-1) + a_{k-1}