前言

我們都見識了不少關(guān)于遞歸與尾遞歸的各種長篇概論，本文將通過對下面幾個問題的直觀體驗，來幫助加深對遞歸的理解。

本文內(nèi)容目錄：

• 什么是調(diào)用棧？
• 什么是遞歸函數(shù)？
• 遞歸的調(diào)用棧是怎樣？
• 尾遞歸的調(diào)用棧是怎樣？
• 為什么說尾遞歸的實現(xiàn)在本質(zhì)上是跟循環(huán)等價？

Game of Thrones.jpg

• 什么是調(diào)用棧？

棧 是一種常見的數(shù)據(jù)結(jié)構(gòu)，具有后進(jìn)先出（LIFO）的特點。
調(diào)用棧 則是計算機內(nèi)部對函數(shù)調(diào)用所分配內(nèi)存時的一種棧結(jié)構(gòu)。

• 什么是遞歸函數(shù)？

遞歸函數(shù) 簡單的講，就是函數(shù)在內(nèi)部調(diào)用自己。

在編寫遞歸函數(shù)的時候，我們要注意組成它的兩個條件，分別是：基線條件 和 遞歸條件 （也叫回歸條件）。

遞歸函數(shù)其實是利用了分而治之的思想（Divide and Conquer D&C），下面用一個簡單的遞歸函數(shù)來說明。

假設(shè)我們現(xiàn)在需要一個遞增函數(shù)increasing(n)，其實現(xiàn)為：

def increasing(n = 0):
    print('n = %d' % n)
    increasing(n + 1)

我們很容易發(fā)現(xiàn)，這樣的代碼會永不休止的執(zhí)行，最后會造成棧溢出，簡單的說就是內(nèi)存滿了。因為根本沒人告訴它什么時候該停下來，所以它不斷的重復(fù)執(zhí)行，造成無限循環(huán)。

假設(shè)遞增的值到100的時候就不再執(zhí)行，則其實現(xiàn)為：

def increasing(n = 0):
    print('n = %d' % n)
    if n == 100: // --> 基線條件
        return
    else: // --> 遞歸條件
        increasing(n + 1)

從上面可以看出，遞歸條件指的是函數(shù)在內(nèi)部繼續(xù)調(diào)用自己，基線條件指的是函數(shù)不再調(diào)用自己的情況。

所謂 Divide and Conquer，分別對應(yīng)的則是遞歸條件和基線條件。

• 遞歸的調(diào)用棧是怎樣？

下面我們通過計算一個數(shù)的階乘的函數(shù)進(jìn)行解釋。它將會有三個不同版本，分別是遞歸求階乘，尾遞歸求階乘，for循環(huán)求階乘。

因為這里要研究遞歸的調(diào)用棧情況，所以我們先來看看遞歸求階乘的實現(xiàn)：

print('##### 遞歸求階乘 #####')
def  fact(n):
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)

print('result = %s' % fact(4))

為了更好的解釋說明，我將上面的代碼略作改動：

print('##### 遞歸求階乘 #####')
def  fact(n):
    if n == 1:
        result = 1
        return result
    else:
        print('current: n = %d, result = %d * fact(%d - 1)' % (n, n, n)) 
        result = fact(n - 1) 
        return n * result 

改動理由：

1. 調(diào)用棧中的函數(shù)都保留計算結(jié)果變量 result，要特別注意的是調(diào)用棧中的各個函數(shù)內(nèi)部的變量對函數(shù)彼此而言是互相隔離無法訪問的。
2. 在遞歸條件中打印活躍期的情況。

所謂活躍期，指的是計算機當(dāng)前所操作的函數(shù)執(zhí)行期。

運行結(jié)果為：

##### 遞歸求階乘 #####
current: n = 4, result = 4 * fact(4 - 1)
current: n = 3, result = 3 * fact(3 - 1)
current: n = 2, result = 2 * fact(2 - 1)
result = 24

其調(diào)用棧情況：

遞歸函數(shù)調(diào)用棧.png

正常情況下，棧頂函數(shù)執(zhí)行完畢后將彈出。但我們卻看到遞歸函數(shù)的調(diào)用不斷的向調(diào)用棧壓入執(zhí)行函數(shù)，那么問題來了，為什么調(diào)用棧前面的函數(shù)"執(zhí)行完畢"后不自動彈出呢？

答案是 棧頂函數(shù)其實并未執(zhí)行完成，因為棧頂函數(shù)的變量result的值尚未確定，它還需要 下一個遞歸函數(shù)返回的值（上下文） 來計算，所以一直處于非活躍期狀態(tài)被保留在調(diào)用棧中。

上面的答案還需完善一下，因為當(dāng)某個棧頂函數(shù)，例如fact(1)，在執(zhí)行到基線條件時，result的值已經(jīng)確定下來，而無需等待下一個遞歸函數(shù)的上下文，所以該棧頂函數(shù)真正執(zhí)行完畢，并彈出調(diào)用棧。又因為下一個棧頂函數(shù)可以拿到已彈棧的函數(shù)返回的上下文，因而當(dāng)彈棧函數(shù)交待完成后，也相繼彈出調(diào)用棧。

• 尾遞歸的調(diào)用棧是怎樣？

我們先來看看尾遞歸求階乘的實現(xiàn)：

print('##### 尾遞歸求階乘 #####')
def fact_tail(n):
    return tail_fact_count(n)

def tail_fact_count(n, result = 1):
    if n == 1:
        return result
    else:
        print('current: n = %d, result = %d' % (n, result))
        print('next: n = %d, result = %d' % (n - 1, result * n))
        print('----------------')
        return tail_fact_count(n - 1, n * result)

print('result = %s' % fact_tail(4))

同樣的，我們將上述代碼略作改動：

print('##### 尾遞歸求階乘 #####')
def fact_tail(n):
    result = tail_fact_count(n)
    return result

def tail_fact_count(n, result = 1):
    if n == 1:
        return result
    else:
        print('current: n = %d, result = %d' % (n, result))
        print('next: n = %d, result = %d' % (n - 1, result * n))
        print('----------------')
        result = n * result
        n = n - 1
        return tail_fact_count(n, result)

print('result = %s' % fact_tail(4))

運行結(jié)果為：

##### 尾遞歸求階乘 #####
current: n = 4, result = 1
next: n = 3, result = 4
----------------
current: n = 3, result = 4
next: n = 2, result = 12
----------------
current: n = 2, result = 12
next: n = 1, result = 24
----------------
result = 24

我們再來看看它的調(diào)用棧情況：

尾遞歸函數(shù)調(diào)用棧.png

尾遞歸函數(shù)調(diào)用棧.png

仔細(xì)對比前面遞歸函數(shù)的調(diào)用棧情況，我們可以看出遞歸與尾遞歸調(diào)用棧的兩個明顯不同點：

1. 尾遞歸的調(diào)用棧明顯比遞歸的調(diào)用棧清爽很多。
2. 尾遞歸彈棧順序是由上至下執(zhí)行；而遞歸彈棧順序是由下至上執(zhí)行的。（這里的彈棧順序指的不是物理順序）

我們再來看看前面遞歸函數(shù)的實現(xiàn)。在遞歸實現(xiàn)中，result的值因為需要 下一個遞歸函數(shù)返回的值 來計算才能確定，所以棧頂函數(shù)（設(shè)A）一直在調(diào)用棧中停留等待下一個棧頂函數(shù)（設(shè)B）的返回值，一旦下一個棧頂函數(shù)（B）返回了確切的result值，那么當(dāng)B交待完成之后就會彈出，所謂交待即是因為上一個棧頂函數(shù)A需要下一個棧頂函數(shù)即B的返回值，當(dāng)A拿到了B的值就是交待完成了。以此類推，遞歸的彈棧順序則如圖所示由下往上彈出。

那么尾遞歸究竟做了什么貓膩？

尾遞歸其實在result的值上做了貓膩。在尾遞歸的實現(xiàn)中，result的值在當(dāng)前棧頂函數(shù)中已經(jīng)確定下來了，并經(jīng)計算后交待給下一個棧頂函數(shù)。所以當(dāng)棧頂函數(shù)完成了它的使命（把result值傳遞給下一個執(zhí)行函數(shù)），它就會愉快的在調(diào)用棧上彈出。

歸納來講:

• 遞歸函數(shù)需要將整個函數(shù)作為上下文來完成 目的。
• 尾遞歸則把 目的 在當(dāng)前函數(shù)中完成，并交待給下一個函數(shù)。

在本例子中的 目的 指的是確定result值。

• 為什么說尾遞歸的實現(xiàn)在本質(zhì)上是跟循環(huán)等價？

按照慣例，先上代碼。但是為了更好的理解與尾遞歸的聯(lián)系，最好還是花個十幾秒思考一下如何實現(xiàn)for循環(huán)求階乘吧~

為了減少篇幅，直接貼上略作修改的代碼：

print('##### for循環(huán)求階乘 #####')
def fact_for(n):
    if n == 1:
        return 1
    else:
        result = 1
        for i in range(n, 0, -1):
            print('current: n = %d, result = %d' % (i, result))
            result = for_fact_count(i, result)
        return result
    
def  for_fact_count(n, result = 1):
    return n * result

print('result = %s' % fact_for(4))

運行結(jié)果為：

##### for循環(huán)求階乘 #####
current: n = 4, result = 1
current: n = 3, result = 4
current: n = 2, result = 12
current: n = 1, result = 24
result = 24

當(dāng)我們思考如何使用for循環(huán)去實現(xiàn)求階乘的過程中，我們會想到用一個變量去存儲計算的值。在上述代碼中指的就是 result (= 1)。

為了便于理解for循環(huán)與尾遞歸，我設(shè)計了這么一個函數(shù) for_fact_count(n, result = 1)，它接收 當(dāng)前result值并經(jīng)計算后刷新result值。

在不影響for循環(huán)的實現(xiàn)我已經(jīng)將其與尾遞歸的實現(xiàn)做了相似的轉(zhuǎn)化（連名字的都好相似啦），所以請開始你的表演，把for循環(huán)求階乘的調(diào)用棧畫出來吧~

結(jié)語：

• 雖說本文使用了Python進(jìn)行編碼解釋，但是目前大多數(shù)編程語言都沒有針對尾遞歸做優(yōu)化，Python解釋器也沒有，所以即便使用了尾遞歸進(jìn)行求階乘，在運行過程中還是會造成棧溢出。而Xcode在debug環(huán)境下不會對尾遞歸做優(yōu)化，需將其設(shè)為release。
• 小生才疏淺陋，文中難免有錯漏之處，請多多指教，感謝您的閱讀。