一、数学归纳法
用于证明断言对所有自然数成立
证明对于n=1成立
证明n>1时：如果对于n-1成立，那么对于n成立
二、数学归纳法例
求证：1+2+3+……+n = n(n+1)/2
1 = 1*2/2
如果1+2+3+……+(n-1) = (n-1)n/2
那么1+2+3+……+n = 1+2+3+……+(n-1)+n = (n-1)n/2+n = (n(n-1)+2n)/2 = n(n+1)/2
int sum(int n) {
if (n == 1) { return 1;}
return sum(n-1) + n;
}
三、递归书写方法
严格定义递归函数的作用，包括参数、返回值、Side-effect
先一般，后特殊
每次调调用必须缩小问题规模
每次问题规模缩小程度必须为1
