前面我們已經(jīng)講了Python中的函數(shù)的用法和屬性，本節(jié)課是函數(shù)部分的最后一講，主要講函數(shù)一個(gè)非常重要的“魔法”，這個(gè)“魔法”能夠解決很多比較難的問(wèn)題，“魔法”的名字叫遞歸。這節(jié)課我們一起了解一下遞歸吧。
如果一個(gè)函數(shù)在內(nèi)部調(diào)用它本身，這個(gè)函數(shù)就是遞歸函數(shù)。遞歸函數(shù)通常會(huì)利用分支結(jié)構(gòu)，其包含兩個(gè)部分：遞歸條件和基線條件。
遞歸條件是指什么情況下函數(shù)會(huì)調(diào)用本身；基線條件是指遞歸的終止條件。
遞歸是程序設(shè)計(jì)中的一個(gè)重要方法，它使許多復(fù)雜的問(wèn)題變得簡(jiǎn)單，容易解決了。
遞歸是一種通過(guò)將大問(wèn)題分解為小規(guī)模同類子問(wèn)題進(jìn)而解決問(wèn)題的方法。它的核心思想是分治策略。分治，即“分而治之”，把一個(gè)復(fù)雜問(wèn)題分成兩個(gè)或更多相同的或者相似的子問(wèn)題，直到最后子問(wèn)題可以簡(jiǎn)單地被直接求解，原問(wèn)題的解也就是子問(wèn)題解的合并。
下面我們使用一個(gè)實(shí)例了解一下遞歸是怎樣寫(xiě)的。
階乘是數(shù)學(xué)上的一種運(yùn)算，它的定義為：一個(gè)正整數(shù)的階乘是所有小于及等于該數(shù)的正整數(shù)的積：
1! = 1
2! = 2 × 1
3! = 3 × 2 × 1
4! = 4 × 3 × 2 × 1
……
我們通過(guò)觀察可以發(fā)現(xiàn)，4! = 4 × 3!、3! = 3 × 2!。即n! = n × (n - 1)!
如果我們定義一個(gè)函數(shù)f(n)用來(lái)計(jì)算階乘，可以將它分解為求解n×f(n-1)。f(n-1)再分解為(n-1)×f(n-2)……以此類推。根據(jù)函數(shù)的定義，1的階乘即為1，最小的子問(wèn)題被解決，原問(wèn)題f(n)即為這些子問(wèn)題的合并。
根據(jù)這樣的思路，我們?cè)诤瘮?shù)f(n)中規(guī)定f(1) = 1，其他情況下返回n * f(n-1)即可。代碼如下：
def f(n): if n == 1: return 1 else: return n * f(n-1)print(f(5))斐波拉契數(shù)列也叫“黃金分割數(shù)列”，數(shù)列從0和1開(kāi)始，從第三項(xiàng)起，每一項(xiàng)都等于前兩項(xiàng)之和。數(shù)列的前n項(xiàng)包括：0,1,1,2,3,5,8,13,21,…。在數(shù)學(xué)上，斐波拉契數(shù)列以遞歸的方法來(lái)定義：
根據(jù)斐波拉契數(shù)列的數(shù)學(xué)定義，可使用遞歸算法計(jì)算該數(shù)列。代碼如下：
# 定義函數(shù)求斐波拉契數(shù)列的第n項(xiàng)def fibonacci(n): if n == 0: return 0 elif n == 1: return 1 else: return fibonacci(n-2) + fibonacci(n-1)# 打印斐波拉契數(shù)列的第0項(xiàng)到第10項(xiàng)for i in range(11): print(fibonacci(i))
漢諾塔（Hanoi Tower）是根據(jù)印度傳說(shuō)形成的數(shù)學(xué)問(wèn)題。有A、B、C三根柱子，A柱子上有n個(gè)圓盤，圓盤從下往上一次變小。要求按照下列規(guī)則將所有圓盤移動(dòng)到C柱子上，最終圓盤在C柱子上也按照從上而下依次變小的規(guī)律排列。問(wèn)：至少移動(dòng)多少次才能移走所有圓盤？
移動(dòng)到過(guò)程中要求小圓盤必須在大圓盤上面，這個(gè)問(wèn)題我們可以找規(guī)律。如果只有1個(gè)圓盤，很明顯，我們把圓盤從A移動(dòng)到C；如果有2個(gè)圓盤，我們把小圓盤從A移動(dòng)到B，大圓盤從A移動(dòng)到C，在把小圓盤從B移動(dòng)到C……
以此類推，我們可以總結(jié)出來(lái)，如果有n個(gè)圓盤，我們先把前面n-1個(gè)圓盤從A移動(dòng)到B，再把第n個(gè)圓盤移動(dòng)到C，最后把前面n-1個(gè)圓盤從B移動(dòng)到C。那么，上面的n-1個(gè)圓盤如何移動(dòng)呢？先把上面第n-2個(gè)移動(dòng)到B，把n-1個(gè)移動(dòng)到C，再把上面的n-2個(gè)移動(dòng)到C。這樣，正好符合遞歸的思想。代碼如下：
# 定義漢諾塔移法的函數(shù)def hanoi(n, a, b, c): # n為漢諾塔層數(shù)，a、b、c為三根柱子 if n == 1: print(a, '-->', c) else: hanoi(n-1, a, c, b) print(a, '-->', c) hanoi(n-1, b, a, c)# 求解4層漢諾塔的移動(dòng)步驟hanoi(4, 'A', 'B', 'C')使用turtle畫(huà)出如圖所示的二叉樹(shù)
編程實(shí)現(xiàn)：
1) 樹(shù)木主干向上生長(zhǎng)，長(zhǎng)度為100；
2) 分形層數(shù)為4，二叉樹(shù)；
3) 第一層樹(shù)枝長(zhǎng)度為60，逐層減小6；
4) 左右樹(shù)枝的傾斜角度為30°；
5) 樹(shù)木的顏色為棕色。
我們對(duì)圖片進(jìn)行分析：除了樹(shù)干外，每一級(jí)的樹(shù)枝都有如下規(guī)律： ① 畫(huà)左側(cè)樹(shù)枝 ②返回 ③畫(huà)右側(cè)樹(shù)枝 ④返回。
畫(huà)到末梢的時(shí)候如果長(zhǎng)度足夠，就繼續(xù)畫(huà)下一級(jí)的樹(shù)枝；如果長(zhǎng)度不夠，則結(jié)束。因此，這個(gè)程序我們可以使用遞歸實(shí)現(xiàn)，代碼如下：
import turtle as tdef binary_tree(n): if n <= 60 - 4 * 6: # 樹(shù)枝共有4層，每層長(zhǎng)度6，畫(huà)完結(jié)束 pass else: t.left(30) #從中間位置向左轉(zhuǎn)30° t.forward(n) # 畫(huà)左側(cè)樹(shù)枝 binary_tree(n-6) # 畫(huà)下一層二叉樹(shù) t.backward(n) # 畫(huà)完返回 t.right(60) #從左側(cè)30°轉(zhuǎn)到右側(cè)30°，共60° t.forward(n) # 畫(huà)左側(cè)樹(shù)枝 binary_tree(n-6) # 畫(huà)下一層二叉樹(shù) t.backward(n) # 畫(huà)完返回 t.left(30) # 轉(zhuǎn)回中間位置t.setheading(90) # 設(shè)置畫(huà)筆方向?yàn)橄蛏蟭.pencolor('brown')t.forward(100) # 畫(huà)樹(shù)干binary_tree(60) #繪制二叉樹(shù)t.hideturtle()t.done()從n個(gè)不同元素中任取m（m≤n）個(gè)元素，按照一定的順序排列起來(lái)，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列。當(dāng)m=n時(shí)所有的排列情況叫全排列。
比如：[1,2,3]的全排列為：
[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,2,1]、[3,1,2]
我們?cè)偈褂?個(gè)數(shù)為例子找一下尋找全排列的規(guī)律：
(1)首先保持1不變，對(duì)2，3，4全排列；
(2)保持2不變，對(duì)3，4全排列；
(3)保持3不變，對(duì)4全排列，4的排列只有一種。得到1，2，3，4
(4)然后3不能不變了，繼續(xù)保持2不變，3，4互換得到1，2，4，3
(5)以1，2打頭的排列完成，接下來(lái)把3換到2的位置，繼續(xù)(3)、(4)的操作
如果有n個(gè)數(shù)的列表進(jìn)行全排列，我們定義perm(list,0,n)函數(shù)：
取出第一個(gè)元素放到最后，即a[1]與a[n]交換，然后遞歸求a[n-1]的全排列
1）如果只有一個(gè)元素n=1，a=[1]則全排列就是[1]
2）如果有兩個(gè)元素n=2，a=[1,2] 則全排列是：
[2,1] -- a[1]與a[2]交換。交換后求a[2-1]=[2]的全排列，歸結(jié)到1)
[1,2] -- a[2]與a[2]交換。交換后求a[2-1]=[1]的全排列，歸結(jié)到1)
3）如果有三個(gè)元素n=3，a={1,2,3} 則全排列是
[[2,3],1] -- a[1]與a[3]交換。后求a[3-1]=[2,3]的全排列，歸結(jié)到2）
[[1,3],2] -- a[2]與a[3]交換。后求a[3-1]=[1,3]的全排列，歸結(jié)到2）
[[1,2],3] -- a[3]與a[3]交換。后求a[3-1]=[1,2]的全排列，歸結(jié)到2）
具體的代碼如下所示：
count = 0 #統(tǒng)計(jì)全排列的個(gè)數(shù)def permutation(n, begin, end): if begin >= end: global count count += 1 print(n) else: i = begin for num in range(begin, end): n[num], n[i] = n[i], n[num] permutation(n, begin+1, end) n[num], n[i] = n[i], n[num]n = [1, 2, 3, 4]permutation(n, 0, len(n))print(count)遞歸優(yōu)點(diǎn)：
代碼可讀性高，程序簡(jiǎn)潔
在解決特殊問(wèn)題如二叉樹(shù)問(wèn)題，漢諾塔問(wèn)題是有著自己天然的優(yōu)勢(shì)
遞歸缺點(diǎn)：
遞歸由于是函數(shù)調(diào)用自身，而函數(shù)調(diào)用是有時(shí)間和空間的消耗的：每一次函數(shù)調(diào)用，都需要在內(nèi)存棧中分配空間以保存參數(shù)、返回地址以及臨時(shí)變量，而往棧中壓入數(shù)據(jù)和彈出數(shù)據(jù)都需要時(shí)間。
遞歸中很多計(jì)算都是重復(fù)的，由于其本質(zhì)是把一個(gè)問(wèn)題分解成兩個(gè)或者多個(gè)小問(wèn)題，多個(gè)小問(wèn)題存在相互重疊的部分，則存在重復(fù)計(jì)算，如斐波那契數(shù)列的遞歸實(shí)現(xiàn)。
調(diào)用?？赡軙?huì)溢出，其實(shí)每一次函數(shù)調(diào)用會(huì)在內(nèi)存棧中分配空間，而每個(gè)進(jìn)程的棧的容量是有限的，當(dāng)調(diào)用的層次太多時(shí)，就會(huì)超出棧的容量，從而導(dǎo)致棧溢出。
1、編程題
使用遞歸的方式計(jì)算1+2+3+……+99+100的和
2、編程題
繪制一個(gè)如圖所示的三叉樹(shù)
1) 樹(shù)木主干向上生長(zhǎng)，長(zhǎng)度為100；
2) 分形層數(shù)為3，三叉樹(shù)；
3) 第一層樹(shù)枝長(zhǎng)度為60，逐層減小10；
4) 第一層每?jī)筛鶚?shù)枝夾角50°，逐層減半；
5) 樹(shù)木的顏色為綠色。
1、D
2、對(duì)
3、參考代碼：
import mathdef avg(*args, **kwargs): a = sum(args) / len(args) key = kwargs.get('appr') if key == 'floor': a = math.floor(a) elif key == 'ceil': a = math.ceil(a) else: a = int(round(a)) return aprint(avg(2,3,4,5,6,22,3,4,5))print(avg(2,3,4,5,6,22,3,4,5,appr='floor'))print(avg(2,3,4,5,6,22,3,4,5,appr='ceil'))4、參考代碼：
def ishealthy(height, weight, gender='male'): bmi = weight / height ** 2 healthy = False if gender == 'male': if bmi >= 20 and bmi <= 25: healthy = True elif gender == 'female': if bmi >= 18 and bmi <= 23: healthy = True else: healthy = None # 如果性別輸入的既不是男也不是女，則不返回結(jié)果 return healthyprint(ishealthy(1.7, 70))print(ishealthy(1.62, 50, 'female')) 聯(lián)系客服
