12函数执行过程_递归函数
目前创新互联建站已为上千余家的企业提供了网站建设、域名、网站空间、网站托管、企业网站设计、青神网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。
目录
函数执行流程:... 1
recursion:... 3
recursion,递归函数
函数执行流程:
http://pythontutor.com/visualize.html#mode=edit
例:
def foo1(b,b1=3):
print('foo1 called',b,b1)
def foo2(c):
foo3(c)
print('foo2 called',c)
def foo3(d):
print('foo3 called',d)
def main():
print('main called')
foo1(100,101)
foo2(200)
print('main ending')
main()
执行过程:
全局帧中生成foo1,foo2,foo3,main函数对象;
main函数调用;
main中查找内建函数print压栈,将常量字符串(main called)压栈,调用函数print,弹出栈顶;
main中全局查找函数foo1压栈,将常量100,101压栈,调用函数foo1,创建栈帧;print函数压栈,字符串和变量b,b1压栈,调用函数,弹出栈顶,返回值;
main中全局查找函数foo2压栈,将常量200压栈,调用函数foo2,创建栈帧;foo3函数压栈,变量c引用压栈,调用foo3,创建栈帧,foo3完成,print函数调用后返回;foo2恢复调用,执行print后返回值;
main中foo2调用结束,弹出栈顶;main继续执行,print函数调用,弹出栈顶,main函数返回;
注:
栈,后进先出;
保护当前函数运行的数据,出现函数调用,依次压栈;
保护现场-->函数压栈-->给函数创建空间frame-->在frame内执行-->依次出栈-->恢复现场;
recursion:
函数直接或者间接调用自身就是递归;
递归需要有边界条件、递归前进段(压栈)、递归返回段(弹出);
递归一定要有边界条件(没有边界条件自己调自己会栈溢出、内存溢出,会将计算机资源耗尽,无限调用);
当边界条件不满足时,递归前进;
当边界条件满足时,递归返回;
直接递归,自己调自己;
间接递归,通过别的函数调用了函数自身;
recursion要求:
一定要有退出条件,递归调用一定要执行到这个退出条件,没有退出条件的递归调用,就是无限调用;
递归调用的深度不宜过深,python对递归调用的深度作了限制,以保护解释器;超过递归深度限制,抛RecursionError: maximum recursion depth excedded超出最大深度;sys.getrecursionlimit(),总共不能超过1000层,自己可用980多,还有其它函数在用;sys.setrecursionlimit(2000),不要改此项,生产中函数复杂,变量、常量各种对象都用内存;
recursion的性能:
循环稍微复杂一些,但只要不是死循环,可以多次迭代直至算出结果;
fib函数代码极简易懂,但只能获取到最外层的函数调用,内部递归结果都是中间结果,且给定一个n都要进行近2n次递归,深度越深效率越低,为了获取fibnacci需要外面再套一个n次的for循环,效率就更低了;
递归还有深度限制,如果递归复杂,函数反复压栈,堆内存很快就溢出了;
recursion总结:
递归是一种很自然的表达,符合逻辑思维;
递归相对运行效率低,每一次调用函数都要开辟栈帧;
递归有深度限制,如果递归层次太深,函数反复压栈,栈内存很快就溢出了;
如果是有限次数的递归,可以使用递归调用,或者使用循环代替,循环的代码稍复杂些,但只要不是死循环,可以多次迭代,直至算出结果;
绝大多数递归,都可使用循环实现;
即使递归代码很简洁,但能不用则不用;
fibnacci number
如果设F(n)为该数列的第n项,n∈N*,即F(n)=F(n-1)+F(n-2);
F(0)=0
F(1)=1
F(n)=F(n-1)+F(n-2)
例:
importdatetime
importsys
start = datetime.datetime.now()
pre =0
cur =1
print(pre,cur,end=' ')
n =35
for_inrange(n-1):
pre,cur = cur,pre+cur
print(cur,end=' ')
print()
delta = (datetime.datetime.now() - start).total_seconds()
print(delta)
print(sys.getrecursionlimit())
例:
importdatetime
start = datetime.datetime.now()
deffib(n):
return1ifn <2elsefib(n-1) + fib(n-2)
foriinrange(35):
print(fib(i),end=' ')
print()
delta = (datetime.datetime.now() - start).total_seconds()
print(delta)
注:
代码虽很精简,但效率低,经测耗时8.127465s;
例:
deffib(n,pre=0,cur=1):
pre,cur = cur,pre+cur
print(cur,end=' ')
ifn ==2:
return
fib(n-1,pre,cur)
fib(10)
注:
改进,与循环思想类似;
参数n是边界条件,用n来计数;
上一次的计算结果,直接作为函数的实参;
效率很高;
和循环比较,性能相近,所以递归并不一定效率低下,但递归有深度限制;
间接递归:
通过别的函数调用了函数自身,如果构成了循环递归调用是非常危险的,但是往往这种情况在代码复杂的情况下,还是可能发生这种调用,要用代码的规范(少用递归,脑跟)来避免这种递归调用的发生;
def foo1():
foo2()
def foo2():
foo1()
foo1()
习题:
1、求n的阶乘?
2、将一个数逆序放入列表中,1234-->[4,3,2,1]?
3、解决猴子吃桃问题?
1、
方一:
deffac(n):
return1ifn ==1elsen * fac(n-1)
print(fac(5))
方二:
deffac(num,mul=1):
mul *= num
ifnum ==1:
returnmul
returnfac(num-1,mul)
print(fac(5))
################
deffac(num,mul=None):
ifmulis None:
mul = [1]
ifnum ==1:
returnmul[0]
mul[0] *= num
fac(num-1,mul)
returnmul
print(fac(5))
################
deffac(num,mul=1):
ifnum ==1:
returnmul
mul *= num
print(mul)
fac(num-1,mul)
returnmul
fac(5)
2、
方一:
defrev(num,lst=None):
iflstis None:
lst = []
x,y =divmod(num,10)
lst.append(y)
ifx ==0:
returnlst
returnrev(x,lst)
print(rev(1234))
方二:
defrev(num,target=[]):
ifnum:
target.append(num[len(num)-1]) #等价于target.append(num[-1:]
rev(num[:len(num)-1])
returntarget
print(rev(str(1234)))
注:
target是位置参数,只不过有默认值;rev(num,*,target),这个target是关键字参数且是keyword-only参数;位置参数的默认值放在__defaults__里,关键字参数的默认值在__kwdefaults__里;
函数对象没变,每次都是rev这个对象,所以该对象的默认值是固定的;
方三:
num =str(1234)
defrev(x):
ifx == -1:
return''
returnnum[x] + rev(x-1)
print(rev(len(num)-1))
3、
defpeach(days=10):
ifdays ==1:
return1
return(peach(days-1)+1) *2
print(peach())
注:
这里必须是10,因为return (peach(days-1)+1)*2立即拿不到结果,必须通过再次进入函数时,判断是不是到了最后一天;即,当前使用的值是由下一次函数调用得到,所以要执行10次函数调用;
###############
defpeach(days=1): #days只用于计数
ifdays ==10:
return1
return(peach(days+1)+1) *2
print(peach())
文章题目:12函数执行过程_递归函数
URL分享:http://myzitong.com/article/ghshsj.html