8.4 遞歸函數(shù)

前面我們學(xué)習(xí)了main函數(shù)可以調(diào)用其它函數(shù)，實(shí)際上函數(shù)也可以調(diào)用自己。還可以調(diào)用自己？

直接或間接的調(diào)用自身的函數(shù)，稱(chēng)為遞歸函數(shù)?？纯蠢觼?lái)了，計(jì)算5的階乘。想想怎么做。最簡(jiǎn)單的使用循環(huán)來(lái)做，代碼如下，這個(gè)寫(xiě)不出來(lái)的話(huà)，doing sit-ups and jumping jacks，200個(gè)怎么樣？

# 方法1：循環(huán)實(shí)現(xiàn)

fac=1

num=5

for i in range(1,num+1):

??? fac=fac *i

print(fac)

?

# 方法2：函數(shù)實(shí)現(xiàn) ?這個(gè)現(xiàn)在也應(yīng)該能做出來(lái)了，想想已知，求什么結(jié)果，設(shè)計(jì)函數(shù)參數(shù)和返回值

def Factorial(num):

??? fac=1

??? for i in range(1,num+1):

??????? fac=fac *i

??? return fac

print(Factorial(5))

?

# 方法3：遞歸函數(shù)實(shí)現(xiàn) ?這個(gè)需要仔細(xì)看看的

def Factorial2(num):

??? if num==1:

??????? return 1

??? else:

??????? return num *Factorial2(num-1)

print(Factorial2(5))

?

我們看一下遞歸函數(shù)實(shí)現(xiàn)的方法，F(xiàn)actorial2(5)，此時(shí)num值是5，所以執(zhí)行循環(huán)體中的else部分，而else部分num *Factorial2(num-1)又調(diào)用了Factorial2，只不過(guò)參數(shù)改成5-1=4。程序執(zhí)行遞歸函數(shù)的調(diào)用過(guò)程請(qǐng)看下圖：

這個(gè)估計(jì)自己看也費(fèi)勁，so 上課講的時(shí)候要認(rèn)真聽(tīng)呦！

如果計(jì)算Factorial2(5)，可以根據(jù)遞歸函數(shù)定義得到計(jì)算過(guò)程如下，使用顏色區(qū)分對(duì)應(yīng)值:

編程練習(xí)：

1. 遞歸函數(shù)fib實(shí)現(xiàn)斐波那契數(shù)列（自己百度一下什么意思吧）

def fib(n):

??? if n==0:

??????? return 0

??? elif n==1:

??????? return 1

??? else:

??????? return fib(n-1) + fib(n-2)

?

print(fib(15))? # 610

?

還想知道到底調(diào)用了多少次fib函數(shù)，改寫(xiě)代碼如下：

def fib(n):

??? global count? #全局變量

??? count = count +1 # 次數(shù)加1，看看到底調(diào)用了多少次fib函數(shù)

?

??? if n==0:

??????? return 0

??? elif n==1:

??????? return 1

??? else:

??????? return fib(n-1) + fib(n-2)

?

count = 0 # 初始賦值0，全局變量

print(fib(5))? # 5

print(count)?? # 15

?

全局變量是什么東西？黑貓警長(zhǎng)（1984年的動(dòng)畫(huà)片）說(shuō)：請(qǐng)看下節(jié)！