資料結構第一章

證明資料結構分析中的結論的兩個常用的方法時歸納法和反證法

歸納法：第一步是證明基準情形，就是确定定理對于某個小的值的正确性，（這一步幾乎是很簡單的

　　　　第二部，進行歸納假設，一般來說，這意味着假設定理對直到某個有限數k的所有的情況都成立的，然後使用這個假設證明定理對于下一個值也是成立的。

反證法：通過假設定理不成立，然後證明該假設導緻某一個已知性質不成立，進而說明原假設是錯誤的。

反證法和歸納法不同處，歸納發從基礎出發，反證法從結論出發。

什麼是遞歸：當一個函數用他自己來定義時就稱為是遞歸。

不是所有的數學遞歸都能有效的由c的遞歸模拟來實作。（如果c中的遞歸沒有基準情況，也是毫無意義的）

遞歸調用将反複進行直到基準情形出現。

編寫遞歸程式的時候，關鍵是記牢遞歸四條基本法則：

1 基準情形　　（總有某些基準情形，它無需遞歸就能解出）

2 不斷推進　　（對于那些需要遞歸求解的情形，每次遞歸調用都必須要使求解狀況朝接近基準情形方向推進）

3 設計法則　　（假設所有的遞歸調用都能運作）

4 合成效益法則。（在求解一個問題的同一執行個體時，切勿在不同的遞歸調用中做重複性的工作）

（有時候不需要遞歸，如果使用了遞歸，則記住第四條，合成效益）