C++課程學習記錄——遞歸

遞歸

概念：

函數直接或間接調用自身的過程

兩個關鍵要素

1.基本情況（遞歸終止條件）：遞歸函數中的一個條件，當滿足該條件時遞歸終止，避免無限遞歸。[直接解決極小規模問題的方法]
2.遞歸表達式（遞歸調用）：遞歸函數中的語句用於解決極小規模的問題，再將子問題的答案合併成為當前問題的答案。

基本結構

返回類型 函數名（參數列表）{
//基本情況（遞歸終止條件）
if（滿足終止條件）{
//返回終止條件的結果
}
//遞歸表達式
else{
//將問題分解為規模更小的問題
//使用遞歸調用解決問題
//返回子問題的結果
}

實現：
1.將大問題分解成規模更小的子問題
2.使用遞歸調用解決每一個子問題
3.通過遞歸終止條件來結束遞歸

注意：
1.確保遞歸一定能到遞歸出口，避免無限遞歸導致超時，超內存和運行錯誤
2.考慮邊界條件，有時遞歸出口不止一個
3.避免不必要的重複計算，儘可能優化遞歸函數性能

遞歸和循環的比較

遞歸

循環

1.直觀簡潔，易於理解和實現

2.適用於問題規模可以通過遞歸調用不斷減小的情況

3.可以處理複雜的數據結構和算法

4.存在棧溢出風險

（棧空間一般只有8MB，所以遞歸層數不易過深，一般不超過1e6層）

1.直接控制流程效率更高

2.適用於問題規模沒有明顯的縮減，或者需要特定的迭代次數

3.適合處理大部分動態規劃問題

在部分情況下遞歸和循環可以互相轉化。

以上就是遞歸部分內容了。
愛心 愛心