遞歸函數

遞歸函數

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函數對象

main函數調用

main中查找內建函數print壓棧，將常量字符串壓棧，調用函數，彈出棧頂

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

main中全局查找foo2函數壓棧，將常量200壓棧，調用foo2，創建棧幀，foo3函數壓棧，變量c引用壓棧，調用foo3，創建棧幀，foo3完成print函數調用返回，foo回復調用，執行print后，返回值。main繼續執行print函數，調出棧頂。main函數返回。

def foo1(b,b1=3):
print(“foo1 called”,b,b1)
foo2(5)
def foo2(a):
print(a)
foo1(2)

foo1函數的字節碼

?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是函數調用，調用完成后，彈出所有函數參數，函數本身關閉堆棧，并推送返回值

15 POP_TCP #刪除頂部（TOS）項目

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

函數直接或則間接調用自身就是遞歸

遞歸需要邊界條件，遞歸前進段，遞歸返回段

遞歸一定要有邊界

當邊界條件不滿足的時候，遞歸前進

當邊界條件滿足的時候，遞歸返回

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

如果設F（n）為該數列的滴n項（n∈N*），那么這句話可以寫成如下形式：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=’ ‘)

遞歸要求

遞歸一定要有退出條件，遞歸調用一定要執行到這個退出條件，沒有退出條件的遞歸調用，就是無限調用

遞歸的深度不宜過深

Python遞歸調用的深度做了限制，以保護解釋器

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

sys.getrecursionlimit()

for 循環

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)

遞歸的性能

循環稍微復雜一些，但是只要不是死循環，可以多次迭代直到算出結果

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

遞歸有深度限制，如果遞歸復雜，函數反復壓棧，內存很快就溢出了

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)

改進：

左邊的fib函數和循環的思想類似

參數n是邊界條件，用n來計數

上一次的計算結果直接作為函數的實參

效率很高

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

遞歸總結

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

遞歸相對運行效率低，每一次調用函數都要開辟棧幀

遞歸有深度限制，如果遞歸復雜，函數反復壓棧，內存很快就溢出了

如果是有次數限制的遞歸，可以使用遞歸調用，或者使用循環代替，循環代碼稍微復雜點，但是只要不是死循環，可以多次迭代直至算出結果

絕大多數遞歸，都可以使用循環實現

即使遞歸代碼很簡潔，但是能不用則不用遞歸

練習：

求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))

將一個數逆序放入列表中，例如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())

?

?

?