遞歸函數(shù)

def foo(b,b1=3):

print(“foo1 called “,b,b1)

def foo2(c):

foo3(c)

print(“foo2 called”,c)

def foo3(d):

print(“foo3 called”)

def mian():

print(“mian called”)

foo1(100,101)

foo2(200)

print(“mian ending”)

mian()

全局幀中生成foo1，foo2，foo3，main函數(shù)對(duì)象

main函數(shù)調(diào)用

main中查找內(nèi)建函數(shù)print壓棧，將常量字符串壓棧，調(diào)用函數(shù)，彈出棧頂

main中全局查找函數(shù)foo1壓棧，將常量100,101壓棧，調(diào)用函數(shù)foo1，創(chuàng)建棧頂，print函數(shù)壓棧，字符串和變量b，b1壓棧，調(diào)用函數(shù)，彈出棧頂，返回值。

main中全局查找foo2函數(shù)壓棧，將常量200壓棧，調(diào)用foo2，創(chuàng)建棧幀，foo3函數(shù)壓棧，變量c引用壓棧，調(diào)用foo3，創(chuàng)建棧幀，foo3完成print函數(shù)調(diào)用返回，foo回復(fù)調(diào)用，執(zhí)行print后，返回值。main繼續(xù)執(zhí)行print函數(shù)，調(diào)出棧頂。main函數(shù)返回。

def foo1(b,b1=3):

print(“foo1 called”,b,b1)

foo2(5)

def foo2(a):

print(a)

foo1(2)

foo1函數(shù)的字節(jié)碼

0 LOAD_GLOBAL 0(print)

3 LOAD_CONST 1(“foo1 ?called”)

6 LOAD_FAST 0(B)

9 LOAD_FAST 1(b1)

12 CALL_FUNCTION 3(3 positional，0 keyword pair)

#CALL_FUNICTION是函數(shù)調(diào)用，調(diào)用完成后，彈出所有函數(shù)參數(shù)，函數(shù)本身關(guān)閉堆棧，并推送返回值

15 POP_TCP #刪除頂部(TOS)項(xiàng)目

16 LOAD_GLOBAL 1(foo2)

19 LOAD_CONST 2(2)

22 CALL_FUNCTION 1(positional,0 keyword pair)

25 POP_TOP

26 LOAD_CONST 0(None)

29 RETURE_VALUE

遞歸Recursion

函數(shù)直接或則間接調(diào)用自身就是遞歸

遞歸需要邊界條件，遞歸前進(jìn)段，遞歸返回段

遞歸一定要有邊界

當(dāng)邊界條件不滿足的時(shí)候，遞歸前進(jìn)

當(dāng)邊界條件滿足的時(shí)候，遞歸返回

斐波那契數(shù)列Fibonacci number：1,1,2,3,5,8,13,21,34,55,89,144，….

如果設(shè)F(n)為該數(shù)列的滴n項(xiàng)(n∈N*)，那么這句話可以寫(xiě)成如下形式：F(n)= F(n-1)+F(n-2)

例子：1

pre ?= 0

cur = 1

print(pre,cur,end=’ ‘)

n = 15

for i in range(n-1):

pre,cur = cur,pre + cur

print(cur,end=’ ‘)

例子：2

def fib(n):

return 1 if n < 2 else fib(n-1) + fib(n-2)

for i in range(5):

print(fib(i),end=’ ‘)

遞歸要求

遞歸一定要有退出條件，遞歸調(diào)用一定要執(zhí)行到這個(gè)退出條件，沒(méi)有退出條件的遞歸調(diào)用，就是無(wú)限調(diào)用

遞歸的深度不宜過(guò)深

Python遞歸調(diào)用的深度做了限制，以保護(hù)解釋器

超過(guò)遞歸深度限制，拋出RecursionError?maxinum recursion depth exceeded超出最大深度

sys.getrecursionlimit()

for 循環(huán)

import datetime

start = datetime.datetime.now()

pre = 0

cur = 1 # No1

print(pre, cur, end=’ ‘)

n = 35

for i in range(n-1): pre, cur = cur, pre + cur

print(cur, end=’ ‘)

delta = (datetime.datetime.now()-start).total_seconds()

print(delta)

遞歸：效率較低

import datetime

n = 35

start = datetime.datetime.now()

def fib(n):

return 1 if n < 2 else fib(n-1) + fib(n-2)

for i in range(n):

print(fib(i), end=’ ‘)

delta = (datetime.datetime.now()-start).total_seconds()

print(delta)

遞歸的性能

循環(huán)稍微復(fù)雜一些，但是只要不是死循環(huán)，可以多次迭代直到算出結(jié)果

fib函數(shù)代碼急件易懂，但是只能獲取到最外層的函數(shù)調(diào)用，內(nèi)部遞歸結(jié)果都是中間結(jié)果，而且給定一個(gè)n都要進(jìn)行2n次遞歸，深度越深效率越低，為了獲取斐波那契數(shù)列需要在外面套一個(gè)n次的循環(huán)，效率就更低了

遞歸有深度限制，如果遞歸復(fù)雜，函數(shù)反復(fù)壓棧，內(nèi)存很快就溢出了

pre = 0

cur = 1

print(pre,cur,end=’ ‘)

def fib(n,pre=0,cur=1):

pre,cur = cur,pre + cur

print(cur,end=’ ‘)

if n == 2:

return

fib(n-1,pre,cur)

fib(7)

改進(jìn)：

左邊的fib函數(shù)和循環(huán)的思想類似

參數(shù)n是邊界條件，用n來(lái)計(jì)數(shù)

上一次的計(jì)算結(jié)果直接作為函數(shù)的實(shí)參

效率很高

和循環(huán)比較，性能相近，所以并不是說(shuō)遞歸一定效率低下，但是遞歸有深度限制

遞歸總結(jié)

遞歸是一種很自然的表達(dá)，符合邏輯思維

遞歸相對(duì)運(yùn)行效率低，每一次調(diào)用函數(shù)都要開(kāi)辟棧幀

遞歸有深度限制，如果遞歸復(fù)雜，函數(shù)反復(fù)壓棧，內(nèi)存很快就溢出了

如果是有次數(shù)限制的遞歸，可以使用遞歸調(diào)用，或者使用循環(huán)代替，循環(huán)代碼稍微復(fù)雜點(diǎn)，但是只要不是死循環(huán)，可以多次迭代直至算出結(jié)果

絕大多數(shù)遞歸，都可以使用循環(huán)實(shí)現(xiàn)

即使遞歸代碼很簡(jiǎn)潔，但是能不用則不用遞歸

練習(xí)：

求n的階層

1種

def fac(n):

if n == 1:

return 1

return n * fac(n-1)

print(fac(5))

2種

def fac1(n,p=1):

if n == 1:

return 1

p *= n

print(p)

fac1(n-1,p)

return n

fac1(5)

3種

def fac2(n,p = None):

if p is None:

p = [1]

if n == 1:

return p[0]

p[0] *= n

#print(p[0])

fac2(n-1,p)

return p

print(fac2(5))

將一個(gè)數(shù)逆序放入列表中，例如1234 => [4,3,2,1]

1

date = str(1234)

def revert(x):

if x == -1:

return ”

return date[x] + revert(x-1)

print(revert(len(date)-1))

2

def revert(n,lst= None):

if lst is None:

lst = []

x,y = divmod(n,10)

lst.append(y)

if x == 0:

return lst

return revert(x,lst)

print(revert(12345))

3

num = 1234

def revert(num,target=[]):

if num:

target.append(num[len(num)-1])

revert(num[:len(num)-1])

return target

print(revert(str(num)))

猴子吃桃NO.10

def peach(day=10):

if day == 1:

return 1

return (peach(day-1)+1)*2

print(peach())

2

def peach(days=1):

if days == 10:

return 1

return (peach(days+1)+1)*2

print(peach())

本文來(lái)自投稿，不代表Linux運(yùn)維部落立場(chǎng)，如若轉(zhuǎn)載，請(qǐng)注明出處：http://www.178linux.com/96275

總結(jié)

以上是生活随笔為你收集整理的linux有没有递归函数,递归函数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。