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