递归函数

递归函数

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

全局帧中生成foo1foo2foo3main函数对象

main函数调用

main中查找内建函数print压栈,将常量字符串压栈,调用函数,弹出栈顶

main中全局查找函数foo1压栈,将常量100,101压栈,调用函数foo1,创建栈顶,print函数压栈,字符串和变量bb1压栈,调用函数,弹出栈顶,返回值。

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 33 positional0 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 number1,1,2,3,5,8,13,21,34,55,89,144….

如果设Fn)为该数列的滴n项(nN*),那么这句话可以写成如下形式:Fn= 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())

 

 

 

本文来自投稿,不代表Linux运维部落立场,如若转载,请注明出处:http://www.178linux.com/96275

联系我们

400-080-6560

在线咨询

工作时间:周一至周五,9:30-18:30,节假日同时也值班

QR code