一、数学归纳法

用于证明断言对所有自然数成立

证明对于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