遞歸
一、函數(shù)調(diào)用函數(shù)
? ? 只要def定義過的函數(shù)對(duì)象都可以被調(diào)用，也可以從函數(shù)里調(diào)用另一個(gè)函數(shù)，例如flower函數(shù)，有參數(shù)size，調(diào)用了star畫紫色五角星，調(diào)用了polygon畫粉色五邊形。
程序：
結(jié)果：
二、遞歸：函數(shù)調(diào)用自己？
? ? 函數(shù)可以調(diào)用自己嗎？從Python語言的函數(shù)定義角度來說，def在前，調(diào)用在后，所以函數(shù)可以調(diào)用自己，稱為“遞歸調(diào)用”。那會(huì)不會(huì)有什么問題？
三、“好”的遞歸：必須有終止條件
? ? 遞歸調(diào)用很有用，但要有個(gè)終止結(jié)束條件，結(jié)束時(shí)不再調(diào)用自身，一般是通過參數(shù)來控制，遞歸調(diào)用時(shí)讓參數(shù)向終止條件演進(jìn)。例子：參數(shù)n，結(jié)束條件是n==0，遞歸調(diào)用時(shí)參數(shù)為n-1，無論多大的n，總會(huì)變?yōu)?。
典型例子：斐波那契數(shù)列
?? 斐波那契數(shù)列的發(fā)現(xiàn)者，是意大利數(shù)學(xué)家列昂納多·斐波那契（Leonardo Fibonacci）。從第3項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和，相鄰兩項(xiàng)之比，無限趨近于“黃金分割數(shù)”0.618….在自然界中有很多實(shí)例，黃金分割比例廣泛應(yīng)用于美術(shù)。
藝術(shù)中的黃金分割Golden Ratio
四、遞歸函數(shù)：fibonacci
? 觀察fibonacci數(shù)列的定義
? 一個(gè)典型的遞歸定義
? 可以寫出遞歸函數(shù)fibonacci
經(jīng)典例子：二叉樹的遞歸分解
? ? 可以把二叉樹分解為三個(gè)部分：樹干、左邊的小樹、右邊的小樹，這樣的分解，正好符合遞歸的定義：對(duì)自身的調(diào)用。
部分程序：
五、分治策略：分而治之Divide and Conquer
? 將復(fù)雜問題分解為幾個(gè)規(guī)模更小問題的組合，是一種直觀而又巧妙的問題解決手段
? “大事化小，小事化了”
? 將問題的規(guī)模縮到足夠小的時(shí)候，許多問題變得顯而易見，甚至無需解決方案
? 分解-解決-合并
典型例子：歸并排序Merge Sort
? ? 歸并排序是遞歸算法，思路是將數(shù)據(jù)表持續(xù)分裂為兩半，對(duì)兩半分別進(jìn)行歸并排序，再把兩半進(jìn)行合并。遞歸的基本結(jié)束條件是：數(shù)據(jù)表僅有1個(gè)數(shù)據(jù)項(xiàng)，自然是排好序的；縮小規(guī)模：將數(shù)據(jù)表分裂為相等的兩半，規(guī)模減為原來的二分之一；調(diào)用自身：將兩半分別調(diào)用自身排序，然后將分別排好序的兩半進(jìn)行歸并，得到排好序的數(shù)據(jù)表。
程序：
練一練
? 畫二叉樹或分形樹
上期參考答案
程序：
import?random
import?turtle
turtle.setworldcoordinates(-100,-100,100,100)
colors?=?['red','orange','yellow','green','blue','purple']
def?polygon(n,size,color):
????t.pencolor(color)
????t.fillcolor(color)
????t.begin_fill()
????for?i?in?range(n):
????????t.forward(size)
????????t.left(360/n)
????t.end_fill()
t?=?turtle.Turtle()
for?j?in?range(50):
????t.penup()
????t.goto(random.randint(-100,100),random.randint(-100,100))
????t.pendown()
????color?=?random.choice(colors)
????n?=?random.randint(4,10)
????size?=?random.randint(5,20)
????polygon(n,?size,?color)
????
????
t.hideturtle()
turtle.done()
???????
結(jié)果：
推薦閱讀
《數(shù)據(jù)科學(xué)與人工智能》公眾號(hào)推薦朋友們學(xué)習(xí)和使用Python語言，需要加入Python語言群的，請(qǐng)掃碼加我個(gè)人微信，備注【姓名-Python群】，我誠邀你入群，大家學(xué)習(xí)和分享。
關(guān)于Python語言，有任何問題或者想法，請(qǐng)留言或者加群討論。