驗證遞歸，可以用數學歸納法：當n=0, 1的時候, 結果正確.假設函數對于n-1是正確的, 那么函數對n結果也正確.如果這兩點是成立的，我們知道這個函數對于所有可能的n都是正確的。如何找到遞歸算法：你必須要示范如何解決問題的一般情況, 通過將問題切分成有限小并更小的子問題，假設n-1成立，那么n需要怎么表示？你必須要示范如何通過有限的步驟, 來解決最小的問題(基本用例)，即0或者1如果這兩件事完成了, 那問題就解決了. 因為遞歸每次都將問題變得更小, 而一個有限的問題終究會被解決的, 而最小的問題僅需幾個有限的步驟就能解決.遞歸的例子：e.g.1 斐波那契數列遞歸法，然而這種解法效率不高！非遞歸法：------------------------------------------------------------------------------------e.g.2階乘遞歸法：long factoria(int n){return n <= 0 ? 1 : factoria(n - 1)*n;}-------------------------------------------------------------------------------------e.g.3漢諾塔有三根桿子A，B，C。A桿上有N個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至C桿：1.每次只能移動一個圓盤.2.大盤不能疊在小盤上面.遞歸法：顯示步驟：void hanoi(int n, char A, char B, char C){if (n == 1)cout << A << "-->" << C << endl;else{hanoi(n - 1, A, C, B);cout << A << "-->" << C << endl;hanoi(n - 1, B, A, C);}}總共需要移動多少次盤子：int count(int n){int c = 0;if (n == 1)c = n;elsec = 2 * count(n - 1) + 1;return c;}----------------------------------------------------------------------------------
