一焦除、數(shù)學(xué)歸納法
用于證明斷言對所有自然數(shù)成立
證明對于n=1成立
證明n>1時：如果對于n-1成立，那么對于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ī)难姘猓縮小程度必須為1
