遞歸算法：
什麼是遞歸呢？其實，遞歸就是函數自己調用自己來解決問題
我們用下面這個例子講解一下遞歸的概念
開盒子找鑰匙
有一天，你需要找一把開啟寶庫的鑰匙，你知道這個箱子能給你一些線索，鑰匙很可能在這個箱子裡，
你知道鑰匙一定在這些盒子裡，你打開了發現，箱子裡有盒子，盒子裡還有盒子，鑰匙到底在哪個盒子裡面呢？
我們用算法來解決這個問題，為了找到這個鑰匙，你將使用什麼算法？
方法一：先發現但未打開的盒子和打開盒子又發現的盒子，處於同一優先級別上，隨機選取盒子打開找鑰匙
方法二：打開盒子如果發現盒子裡還有盒子，那就繼續打開這個盒子，一直到盒子裡沒盒子也沒鑰匙時，再向上找之前未打開的盒子打開
兩種方法的偽代碼：
後面這種方法中，便利用了遞歸算法，自己調用自己，從代碼中看到，是不是遞歸的方法更加清晰一些。
特點：遞歸只是讓解決方案更清晰，並沒有性能上的優勢。
基線條件和遞歸條件：
對於循環，我們都知道有一個循環條件，一旦不滿足這個條件，算法會停止循環跳出。同理為了避免遞歸算法一直遞歸成無限循環，它也需要設置一定的停止條件。像找鑰匙這個例子，如果沒找到鑰匙，但打開了所有的盒子，沒有未打開的盒子，就是停止條件。
遞歸條件指的是函數調用自己，而基線條件則指的是函數不再調用自己，從而避免形成無限循環。
棧
棧是一種數據結構，它主要的特點是隻能從一端插入和彈出，存儲進棧的操作具有一定的順序，先進後出，後進先出。
先介紹一下棧的調用，以下面這段程序為例：
當調用主函數greet（name）時，計算機將首先為該函數調用分配一塊內存。
假設name="maggie",這需要存儲到計算機中
當調用greet2（name）時，同樣為greet2分配內存，第二個內存塊位於第一個內存塊上面
當執行輸出“how are you, maggie?”時，然後從greet2函數調用返回。此時，棧頂的內存塊被彈出。
這時，棧頂是greet函數，說明又回到了greet函數內，接著執行print，再執行bye(),進入bye()函數，將bye函數存儲進棧頂。
執行bye函數，打印ok bye!，並從這個函數返回，再將bye函數彈出棧，返回到greet函數，
這時，greet函數內已經沒有需要執行的操作，所以將greet彈出，釋放棧，棧控制這這裡面的運行順序。
遞歸調用棧
遞歸也需要調用棧，對於下面這個函數
對於fact(3)的棧調用順序如下:
棧的優點：
功能清晰，實現簡單
棧的缺點：
存儲詳盡的信息可能佔用大量的內存。每個函數調用都要佔用一定的內存，如果棧很高，就意味著計算機存儲了大量函數調用的信息。在這種情況下可能需要重新編寫代碼，轉而使用循環，或者使用尾遞歸。
這是書籍《算法圖解》第三章的內容的學習筆記，前面兩章內容見前面幾篇筆記，《算法圖解》可以幫助瞭解簡單的算法知識，如需深入學習可以看看《算法導論》歡迎一起學習~
閱讀更多 AI深度學習求索 的文章
