算法圖解讀書筆記 第3章 遞歸

遞歸

遞歸是很多算法都使用的一種方法，學習如何将問題分為基線條件和遞歸條件。

3.1 遞歸

例子，盒子裡面找鑰匙（盒子裡面還有盒子）

方法一：

①建立一個要查找的盒子堆

②從盒子堆取出一個盒子，在裡面找

③如果找到的是盒子，就将其加入盒子堆中，以便以後再查找

④如果找到鑰匙，大功告成

⑤回到第二步

方法二：

①檢查盒子裡的每樣東西

②如果是盒子就回到第一步

③如果是鑰匙就大功告成

其實第一種方法使用的是while循環，隻要盒子堆不空，就從中取出一個盒子，并在其中仔細查找。第二種方法就是遞歸了，函數調用自己。

3.2 基線條件和遞歸條件

編寫遞歸時必須告訴它何時停止，正因如此每個遞歸都有兩部分：基線條件和遞歸條件。遞歸條件是指函數調用自己，而基線條件則是函數不在調用自己，進而避免無線循環。

3.3 棧

調用棧不僅對程式設計很重要，使用遞歸時也必須了解這個概念。

3.3.1 調用棧

在計算機内部使用被稱為調用棧的棧。

3.3.2 遞歸調用棧

遞歸函數也使用調用棧。使用棧很友善，但也要付出代價；存儲詳盡的資訊可能占用大量的記憶體。每個函數調用都要占用一定的記憶體，如果棧很高 ，就意味着計算機存儲了大量函數調用的資訊。這種情況下有兩種選擇：

①重新編寫代碼，轉而使用循環

②使用尾遞歸。

小結