算法圖解學習筆記（三）——遞歸

一、遞歸的引入

小故事：一個盒子裡還有盒子，盒子的盒子裡面還有盒子，祖母說鑰匙就在其中某個盒子中，為找到鑰匙，用什麼算法

第一種方法：----普通while循環

第二種方法：---遞歸，函數調用自己

總結：其實遞歸方案的引用，對程式的性能沒什麼影響，隻是友善了解，是以具體應用中，需要考慮實際場景來使用遞歸

二、基線條件和遞歸條件

例如：我們編寫一個倒計時的函數

def countdown(i):
    print(i)
    countdown(i-1)
countdown(2)
           

他會一直運作，因為我們沒有告訴它什麼時間結束，是以每個遞歸函數都有兩個部分組成：基線條件、遞歸條件，遞歸條件是指自己調用自己，基線條件是指函數不再調用自己，進而避免形成無限循環

那麼上面的函數添加了基線條件以後是這樣的：其中 if 條件就是基線條件，else後面就是遞歸條件

def countdown(i):
    print(i)
    if i<=1:
        return
    else:
       countdown(i-1)
countdown(10)
           

三、棧

1、棧是由一系列對象組成的一個集合，這些對象滿足後近先出(LIFO)的原則。 和自動販賣機賣水一樣，也就是删除和插入都是最後一個。

2、調用棧：計算機在内部使用被稱為調用棧的棧

3、執行遞歸的過程可以是調用棧的過程：例如遞歸函數的調用棧，5！=5*4*3*2*1

def fact(x):
    if x==1:
        return 1
    else:
        return  x*fact(x-1)
i=int(fact(5))
print(i)
           

---執行遞歸的過程可以是調用棧的過程, 如下圖， 調用的函數的執行記憶體都存放在棧對象中，執行完後被釋放。

---使用棧雖然很友善，但是也要付出代價，存儲詳盡的資訊可能占用大量的記憶體，每個函數調用都要占用一定的記憶體，如果棧很高，就意味着計算機存儲了大量函數調用的資訊，是以我們就需要重新編寫代碼。或者使用循環，或者使用尾遞歸