6.9　遞歸函數(shù)

Python語言中，如果一個(gè)函數(shù)在調(diào)用時(shí)直接或間接地調(diào)用了自身，就稱為函數(shù)的遞歸調(diào)用，該函數(shù)就稱為遞歸函數(shù)。

由于函數(shù)在執(zhí)行時(shí)都會(huì)在棧中分配好自己的形參與局部變量副本，這些副本與該函數(shù)再次執(zhí)行時(shí)不會(huì)發(fā)生任何的影響，因此使得遞歸調(diào)用成為了可能。

6.9.1　使用遞歸函數(shù)

遞歸是指在函數(shù)執(zhí)行過程中再次對(duì)自己進(jìn)行調(diào)用。例如：

    def f()
    {
    y=f();
    return y;
    }

該程序的執(zhí)行過程如圖6-39所示。

圖6-39　遞歸過程

在函數(shù)f()中按照由上至下的順序進(jìn)行執(zhí)行，當(dāng)遇到對(duì)自身的調(diào)用時(shí)，再返回函數(shù)f()的起始處，繼續(xù)由上至下進(jìn)行處理。

例如，計(jì)算階乘n! = 1 * 2 * 3 * ... * n，用函數(shù)f (n)表示，可以看出：

    f (n) = n! = 1 * 2 * 3 * ... * (n-1) * n = (n-1)! * n = fact(n-1) * n

所以，f (n)可以表示為n*fact(n-1)，只有n=1時(shí)需要特殊處理。

【例6.7】使用函數(shù)的遞歸調(diào)用，對(duì)n的階乘進(jìn)行求解并輸出結(jié)果（源代碼\ch06\6.7.py）。

保存并運(yùn)行程序，結(jié)果如圖6-40所示。

圖6-40　運(yùn)行結(jié)果

本示例演示了如何對(duì)函數(shù)進(jìn)行遞歸調(diào)用。在上面的代碼中，首先定義函數(shù)f()，該函數(shù)用于對(duì)n的階乘進(jìn)行求解。其中，若n=1，則階乘為1；否則就調(diào)用函數(shù)f()，對(duì)n的階乘進(jìn)行求解，最后輸出計(jì)算結(jié)果。

求n的階乘即計(jì)算“n* f(n-1)”的值。6的階乘的計(jì)算過程如下：

    ===>f(6)
    ===>6*f(5)
    ===>6*5*f(4)
    ===>6*5*4 *f(3)
    ===>6*5*4 * 3 *f(2)
    ===>6*5*4 * 3 * 2*f(1)
    ===>6*5*4 * 3 * 2*1
    ===>720

6.9.2　利用遞歸函數(shù)解決漢諾塔問題

漢諾塔問題源于印度一個(gè)古老的傳說：有三根柱子，首先在第一根柱子從下向上按照大小順序擺放64片圓盤；然后將圓盤從下開始同樣按照大小順序擺放到另一根柱子上，并且規(guī)定小圓盤上不能擺放大圓盤，在三根柱子之間每次只能移動(dòng)一個(gè)圓盤；最后移動(dòng)的結(jié)果是將所有圓盤通過其中一根柱子全部移動(dòng)到另一根柱子上，并且擺放順序不變。

以移動(dòng)三個(gè)圓盤為例，漢諾塔的移動(dòng)過程如圖6-41所示。

圖6-41　漢諾塔移動(dòng)過程

【例6.8】使用遞歸算法解決漢諾塔問題，并將解決步驟輸出在屏幕上（源代碼\ch06\6.8.py）。

保存并運(yùn)行程序，結(jié)果如圖6-42所示。

圖6-42　運(yùn)行結(jié)果

在上面的代碼中，首先定義move()函數(shù)，該函數(shù)有4個(gè)形參，分別是n、a、b、c，其中a、b、c用于模擬三根柱子。然后通過判斷n的值分別進(jìn)行不同的移法，若n為1，則可以直接將圓盤從a柱子移動(dòng)到c柱子；若n不為1，則對(duì)move()函數(shù)進(jìn)行遞歸調(diào)用。完成兩個(gè)步驟：第一步將（n-1）個(gè)圓盤從a柱子通過c柱子擺放到b柱子上；第二步將第（n-1）個(gè)圓盤移動(dòng)到b柱子后，由b柱子通過a柱子再移動(dòng)到c柱子上，如此循環(huán)，最后完成轉(zhuǎn)移。

6.9.3　防止棧溢出

使用遞歸函數(shù)需要防止棧溢出。在計(jì)算機(jī)中，函數(shù)調(diào)用是通過棧（stack）這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的，每當(dāng)進(jìn)入一個(gè)函數(shù)調(diào)用，棧就會(huì)加一層棧幀，每當(dāng)函數(shù)返回，棧就會(huì)減一層棧幀。因?yàn)闂５拇笮〔皇菬o限的，所以遞歸調(diào)用的次數(shù)過多，會(huì)導(dǎo)致棧溢出。

例如：

運(yùn)行結(jié)果如圖6-43所示。

圖6-43　運(yùn)行結(jié)果

從運(yùn)行結(jié)果可以看出，執(zhí)行出現(xiàn)異常，提示超過最大遞歸深度。

解決遞歸調(diào)用棧溢出的方法是通過尾遞歸優(yōu)化。事實(shí)上，尾遞歸與循環(huán)的效果是一樣的，所以把循環(huán)看成是一種特殊的尾遞歸函數(shù)也是可以的。

尾遞歸是指在函數(shù)返回時(shí)調(diào)用函數(shù)本身，并且return語句不能包含表達(dá)式。這樣，編譯器或解釋器就可以對(duì)尾遞歸進(jìn)行優(yōu)化，使遞歸本身無論調(diào)用多少次，都只占用一個(gè)棧幀，不會(huì)出現(xiàn)棧溢出的情況。

上面的f(n)函數(shù)，由于return n * f(n - 1)引入了乘法表達(dá)式，因此就不是尾遞歸了。要改成尾遞歸方式，就需要多一些代碼，主要是把每一步的乘積傳入到遞歸函數(shù)中：

可以看到，return f1(num - 1, num * product)僅返回遞歸函數(shù)本身。其中，num - 1和num *product在函數(shù)調(diào)用前就會(huì)被計(jì)算，不影響函數(shù)調(diào)用。

f(6)對(duì)應(yīng)的f1(6,1)的調(diào)用如下：

    ===> f1(5, 1)
    ===> f1(5, 6)
    ===> f1(4, 30)
    ===> f1(3, 120)
    ===> f1(2, 360)
    ===> f1(1, 720)
    ===> 720

尾遞歸調(diào)用時(shí)，若進(jìn)行了優(yōu)化，則棧不會(huì)增長，因此無論調(diào)用多少次都不會(huì)導(dǎo)致棧溢出。