python編程入門十三：遞回

第十三章：遞回

說到遞回，或許你也聽說過遞推，這兩個概念其實應該算到演算法的行列，在python編程入門的教程中我們也只是簡單的講一下，知道這個概念以及可以簡單的應用就可以；本章其實也應該屬于函式的范疇，因為只要用到遞回，就肯定需要借助函式，所以本章也作為函式的一個延伸和應用來講，

13.1 遞回、遞推傻傻分不清楚

首先我們通過一個數學問題來深入區分一下遞推和遞回，階乘這個概念想必每個人在初高中就已經開始接觸了，如果我們說5的階乘，那結果則是1 x 2 x 3 x 4 x 5所得到的積；以此類推，一個n的階乘則是從1 x 2 x 3 x … x n，讓我們算階乘的方式，在上學時可能只有手算或者是使用計算器來逐一做乘法運算，但現在我們使用編程語言卻可以只用幾行代碼來實作所有數字階乘的運算，接下來我們分別使用遞推和遞回來撰寫求階乘的程式，

13.1.1 使用遞推進行的階乘運算

首先我們通過概念來了解一下什么是遞推：

遞推是按照一定的規律來計算序列中的每個項，通常是通過計算前面的一些項來得出序列中的指定項的值，其思想是把一個復雜的龐大的計算程序轉化為簡單程序的多次重復，該演算法利用了計算機速度快和不知疲倦的機器特點，

接下來我們直接撰寫并分析下面通過遞推來實作求階乘演算法的代碼：

def factorial(n):
    number = 1
    for i in range(1, n + 1):
        number = number * i
    return number

print(factorial(5))

結果：

120

上面的代碼是通過遞推的方式來實作對5做的階乘，可以發現這塊代碼的邏輯很簡單，我們首先定義一個初始值為1的number變數（初始化為1的原因是1乘以任何數都為這個數，不會對結果有影響），然后我們使用for回圈，同樣需要確定for回圈中i要從1開始賦值（不從0開始是因為0乘以任何數都為0），然后for回圈的最后一個數字應該是n，所以這里需要寫入n + 1（for回圈的用法是包含開始的數，不包含結束的數字，也就是前閉后開），這樣就可以實作從1 x 2 到 x n的功能；讓我們感覺用起來比較簡單的原因就是遞推的程序就像是一條向一個方向延伸的直線，規律明了，路徑清晰；但接下來要說的遞回就沒這么簡單了，

13.1.2 使用遞回進行的階乘運算

接下來我們還是先看一下遞回的說法：

遞回，在數學與計算機科學中，是指在函式的定義中使用函式自身的方法，遞回一詞還較常用于描述以自相似方法重復事物的程序，例如，當兩面鏡子相互之間近似平行時，鏡中嵌套的影像是以無限遞回的形式出現的，也可以理解為自我復制的程序，

比如像下圖一樣的情景我們肯定見到過：

另外，我們在看一些主播打開直播軟體的時候也會看到這樣一層層重復畫面的情景；甚至我還記得在某個星級飯店上廁所時，整個廁所的四面都是全尺寸的玻璃，映射出無數個我陪我一起上廁所，真的是貼心，

這些類似的情景可以作為遞回的可視化概念來進行理解，當然我們還是通過求階乘的方式來分析代碼，從而對遞回有一個更好的認識：

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))

結果：

120

通過使用遞回的方式，同樣可以得到正確的答案，并且看似代碼更加簡潔，我們來分析一下上述代碼：當我們向factorial函式內傳入數字5之后，首先會通過if陳述句來進行判斷，如果滿足n == 1，則直接回傳數字1；否則，會回傳n * factorial(n - 1)；這種方式在你第一眼看來肯定會有些奇怪，但這就是遞回的普遍特性，就像上文對遞回的解釋：遞回通常表現為函式呼叫函式本身的一種方法；所以factorial(n - 1)又會繼續展開，此時會向factorial函式傳入數字4，同樣不滿足n == 1，所以還會進一步回傳factorial(n - 1)，直到 n == 1，回傳數字1為止，我們可以通過下圖來理解當前的遞回流程：

這個程序并不像是遞推一樣，只有一條直線延伸的邏輯，而是到直線“盡頭”又一層一層回傳結果的一個程序；所以遞回相對于遞推來說，就仿佛是多拐了一個彎兒，雖然可以實作同樣的功能，并且難度還比遞推要大，但之后有些場合下，遞回才是天才程式員的首選；所以遞回，是變成天才程式員的第一步，

13.2 兔子，兔子，又是兔子

講到遞回，我們必不可少的會講到另一個關于兔子的數學案例–斐波那契數列；問題描述是這樣的：如果一對兔子在出生兩個月后就有繁殖能力，之后的每個月都能生出一對小兔子，假設生出的每對兔子都是雌雄各一只，并且所有兔子都不會死去，那么一年之后這一家族會有多少對兔子，

我們首先通過下面一張圖片來進行可視化的觀察：

首先第A對兔子在前兩個月是沒有繁殖能力的，所以均是一對兔子；然后在第三個月，由第A對兔子繁殖出第B對兔子；到第四個月，第B對兔子依舊沒有繁殖能力，由第A對兔子又繁殖出第C對兔子，所以在第四個月，有三對兔子共存；所以資料統計如下圖所示：

我們通過對上圖表格資料的分析，可以發現一個很明顯的規律：從3月份開始，每月的兔子總對數都是前兩個月的和，因此可以得到以下分段函式：

13.2.1 遞推方式的斐波那契數列

同樣，遞回能完成的功能，使用遞推會更好理解一些；我們先通過遞推的方式來撰寫一個斐波那契數列的函式：

def Fib(n):
    f1 = 1
    f2 = 1
    if (n <= 2):
        return 1
    else:
        for i in range(n - 2):
            f3 = f1 + f2
            f1 = f2
            f2 = f3
        return f3

print(Fib(10))

然后我們分析上述代碼，我們定義了一個用于求斐波那契數列的一個遞推函式，首先定義f1和f2的初始值都是1，并且使用if判斷當輸入的n小于或等于2時，都得到結果1，所以直接return 1；在n大于2時則滿足Fib(n) = Fib(n -1 ) + Fib(n - 2)的運算式，所以借助for回圈進行遞推，另外for的回圈次數受到n的影響，需要使用n減去已經初始化為1的前兩個資料的回圈次數，接下來for回圈內的陳述句就像是推箱子一樣，f3為f1和f2的和，然后f1和f2分別向前推進一位，通過遞推就可以得到相應的斐波那契數列，

13.2.2 遞回方式的斐波那契數列

遞推的方式清晰易懂，但遞回才是我們的最終選擇，接下來我們先看一下使用遞回求斐波那契數列的原理圖：

通過原理圖可以發現整個遞回流程是先順向拆解，然后逆向回傳求和，確實在思路上是要比遞推要復雜一些的，然后我們根據原理圖撰寫遞回求斐波那契數列的程式：

def Fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return Fib(n - 1) + Fib(n - 2)

print(Fib(10))

通過對比遞推和遞回的代碼，我們可以發現很明顯的一個規律；遞推的實作原理很簡單，但我們需要付出更多代碼量，遞回的原理相比較復雜，但我們卻可以使用較少的代碼來完成，就好像把一個比較重的任務直接丟給遞回來做：“自己呼叫自己去吧，我就不管了”，

除了我們所說的遞回邏輯復雜，但代碼較少并清晰的特點之外，我們還有必要說一下遞回的缺點，多數情況下，遞回的效率是要比遞推要低很多的，從兩者的運行原理就可以看出來，遞回需要不斷的呼叫自身，確實會比遞推要執行更多的陳述句，我們知道每執行一行陳述句都是消耗時間的，代碼少的話幾乎感受不到，但如果我們使用遞回來算100個月之后的兔子數量，兩者的運行時間就會有明顯的差別了，所以聽我一句勸，并不是使用遞回就可以稱神了，而是需要在適合的情況下來利用好這個神奇的演算法，當然這需要大量的專案經驗，當前只有能理解并簡單使用遞回演算法就足夠了，

最后再總結一下遞回需要滿足的三個條件：

1.必須有一個明確的結束條件；
2.每次進入更深一層遞回時，問題規模相比上次遞回都應有所減少
3.相鄰兩次重復之間有緊密的聯系，前一次要為后一次做準備