我們花了大半時間在討論資料結構，終於從今天開始我會開始跟大家介紹我們常用的演算法，希望讀者們都還可以跟上這幾天的步調，好了那就讓我們繼續往下看下去吧！

為了讓大家可以更深刻的了解遞迴，我希望可以先從Call Stack說起，當大家有了Call Stack的概念再去學習遞迴，遇到Bug的時候會比較容易去除蟲呦。

本篇會以比較底層的角度去看遞迴的運作原理，下一篇才會更深入的去探索遞迴的思想。

Call Stack

每當我們(主或副)函式在執行且還沒結束時，都會在記憶體上生成Call Stack，沒錯這個Stack就是我們之前學到先進後出的那個Stack，這個Call Stack會決定現在我應該執行哪一個副函式，還記得Stack的特性嗎？Call Stack一樣會先執行Stack最上面的函式，我們來看一個例子。

def main():
    print(“hello in main”)
    fun()
    print(“end”)

def fun():
    print(“hello in fun”)

我們程式一開始會遇到main這個函式，所以我們會在Call Stack上生成並且執行它，執行完print("hello in main")我們遇到fun()這個副函式，由於main函式還沒結束所以Call Stack不會將它移除，而是將Fun函式加到Main函式上面並且執行fun函式，執行完print(“hello in fun”)後我們可以發現FUN函式已經執行完了，所以將他從Call Stack上拿掉。然後我們發現現在最上面的是main函式，於是我們再回來繼續執行main函式直到它結束，然後再從Call Stack移除，這樣就跑完我們整個程式了。

甚麼是遞迴

Recursion中文叫做遞迴，其實嚴格來說，遞迴並不算是一種演算法，它比較像是一種思想，一種我們看待問題的思想。
今天不會講到關於遞迴思想的部分，我們會注重在遞迴跟Call Stack的關係以及它的運作模式。

程式中的遞迴

遞迴的實作其實相對單純，就是一個「函式呼叫自己本身」僅此而已。

def my_resursion_fun():
    my_recursion_fun()

剛開始學程式的同學一定會覺得媽呀，副函式還可以這樣用啊！不用擔心，這也是我一開始的疑惑，在往下之前，我們先來看看當我們遞迴的程式被呼叫時，電腦到底做了甚麼事。

從Call Stack看遞迴

介紹完Call Stack後我們再回過頭來看看當自己呼叫自己的函式出現，Call Stack會怎麼運作呢？

def my_resursion_fun():
    print(“In to function”)
    my_recursion_fun()

當我開始執行這隻程式的時候，Call Stack會生成一個my_resursion_fun()等到它執行結束後才會pop出Stack，接著會執行print(“In to function”) 完後會執行另一個my_recursion_fun()，這時候我的Call Stack會將新的my_recursion_fun()加到上面，接著開始執行它，接著會執行新的my_recursion_fun()的print(“In to function”)，遇到my_recursion_fun()後又加一個更新的my_recursion_fun()到Call Stack的上方。



等等這樣不對吧 ! 沒錯！因為如果你真的直接執行，會遇到「call stack is not deep enough」這種錯

不同語言可能不太一樣，但是大同小異，意思就是Call Stack不夠大，廢話~我們剛剛的例子就是給Call Stack無限的一直在上面堆疊，那該怎麼辦呢？

Base Case

剛剛的問題點在於，我們並沒有設置一個條件讓他停下來，這樣他才能從Call Stack上被移除進而停止那種無窮的狀態。那我們該怎麼做呢？當然就是設置條件拉！這個「條件」我們稱為Base Case
現在我把我的程式改成這樣

def my_resursion_fun():
    print(“In to function”)
    if n == 1:
        return
    my_resursion_fun()

先別管其他部分，關注在n==1就好，所以這邊我們可以發現，當n==1時這個function就會完成，也就會從Call Stack上被pop然後他的下一層也都會陸續從Stack被pop出來，這樣就會避免無窮的狀態。

然而，這個n怎麼來？您可以設置成global variable，但更好的做法是，從上一層的狀態傳下來，但記得為了要避免進入無窮的狀態，我們的n要不斷去接近n==1，說來很玄，大家看看這個例子就好懂許多。

def my_resursion_fun(n):
    print(“Into function”)
    if n == 1:
        return
    my_recursion_fun(n-1)

我們可以發現每次進入下一個Call Stack我都把n減1，然後當符合Base Case (n==1)條件後就會被pop出來，這樣大家就都已經會複雜的Call Stack觀念了。
這邊的n其實更多時候我會稱作它是一個「狀態」，至於為什麼是狀態，希望大家不要急，要等到後面的篇幅大家才會慢慢有感覺了。

結論

今天我們介紹了Call Stack，更具體的體會大家可以在自己開發環境上的IDE去看，我本人是用VS CODE開發，左下角都會有Call Stack的資訊給使用者看。
我們還從Call Stack去看最簡單的遞迴定義「自己呼叫自己」，然後我們發現，一開始的寫法會導致我們Call Stack不斷增加發生錯誤，所以我們要定義一個Base Case在每一次的遞迴中去接近那個Base Case，這樣才能讓我們Call Stack裡的副函式結束然後pop出Call Stack。