《算法圖解》第三章遞歸學習心得

1、問題的引入

盒子裡有盒子， 而盒子裡的盒子又有盒子。 鑰匙就在某個盒子中。 分别用while循環和遞歸解決這個問題（僞代碼）：

while循環：

def look_for_key(main_box):
    pile=main_box.make_a_pile_to_look_through()
    while pile is not empty:
        box=pile.grab_a_box()
        for item in box:
            if item.is_a_box():
                pile.append(item)
            elif item.is_a_key():
                print("found the key")
           

遞歸：

def look_for_key(box):
    for item in box:
        if item.is_a_box():
            look_for_key(item)
        elif item.is_a_key():
             print("found the key")
           

2、兩個基本概念

基線條件 （base case） 和遞歸條件 （recursive case）。遞歸條件指的是函數調用自己， 而基線條件則指的是函數不再

調用自己， 進而避免形成無限循環。

3、棧

python中調用棧的例子：

def greet(name):
    print("hello,"+name+"!")
    greet2(name)
    print("getting ready to say bye...")
    bye()

def greet2(name):
    print("how are you ,"+name+"?")
    
def bye():
    print("ok bye!")
           

輸出：

hello,maggie!
how are you ,maggie?
getting ready to say bye...
ok bye!
           

4、小結

1. 遞歸指的是調用自己的函數。
2. 每個遞歸函數都有兩個條件： 基線條件和遞歸條件。
3. 棧有兩種操作： 壓入和彈出。
4. 所有函數調用都進入調用棧。
5. 調用棧可能很長， 這将占用大量的記憶體。