一、數(shù)學(xué)歸納法

用于證明斷言對(duì)所有自然數(shù)成立

證明對(duì)于n=1成立

證明n>1時(shí)：如果對(duì)于n-1成立，那么對(duì)于n成立

二、數(shù)學(xué)歸納法例

求證：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;

}

三、遞歸書寫方法

嚴(yán)格定義遞歸函數(shù)的作用，包括參數(shù)、返回值、Side-effect

先一般，后特殊

每次調(diào)調(diào)用必須縮小問題規(guī)模

每次問題規(guī)?？s小程度必須為1