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)

例：

import datetime
import sys

 start = datetime.datetime.now()
 pre = 0
cur = 1
print(pre,cur,end=' ')
 n = 35

for _ in range(n-1):
     pre,cur = cur,pre+cur
     print(cur,end=' ')
print()

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

print(sys.getrecursionlimit())

例：

import datetime

 start = datetime.datetime.now()
def fib(n):
     return 1 if n < 2 else fib(n-1) + fib(n-2)

for i in range(35):
     print(fib(i),end=' ')
print()

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

注：

代码虽很精简，但效率低，经测耗时8.127465s；

例：

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

注：

改进，与循环思想类似；

参数n是边界条件，用n来计数；

上一次的计算结果，直接作为函数的实参；

效率很高；

和循环比较，性能相近，所以递归并不一定效率低下，但递归有深度限制；

间接递归：

通过别的函数调用了函数自身，如果构成了循环递归调用是非常危险的，但是往往这种情况在代码复杂的情况下，还是可能发生这种调用，要用代码的规范（少用递归，脑跟）来避免这种递归调用的发生；

def foo1():

    foo2()

def foo2():

    foo1()

foo1()

习题：

1、求n的阶乘？

2、将一个数逆序放入列表中，1234-->[4,3,2,1]？

3、解决猴子吃桃问题？

1、

方一：

def fac(n):
     return 1 if n == 1 else n * fac(n-1)

print(fac(5))

方二：

def fac(num,mul=1):
     mul *= num
     if num == 1:
         return mul
     return fac(num-1,mul)

print(fac(5))

################

def fac(num,mul=None):
     if mul is None:
         mul = [1]
     if num == 1:
         return mul[0]
     mul[0] *= num
     fac(num-1,mul)
     return mul

print(fac(5))

################

def fac(num,mul=1):
     if num == 1:
         return mul
     mul *= num
     print(mul)
     fac(num-1,mul)
     return mul

 fac(5)

2、

方一：

def rev(num,lst=None):
     if lst is None:
         lst = []
     x,y = divmod(num,10)
     lst.append(y)
     if x == 0:
         return lst
     return rev(x,lst)

print(rev(1234))

方二：

def rev(num,target=[]):
     if num:
         target.append(num[len(num)-1])   #等价于target.append(num[-1:]
         rev(num[:len(num)-1])
     return target

print(rev(str(1234)))

注：

target是位置参数，只不过有默认值；rev(num,*,target),这个target是关键字参数且是keyword-only参数；位置参数的默认值放在__defaults__里，关键字参数的默认值在__kwdefaults__里；

函数对象没变，每次都是rev这个对象，所以该对象的默认值是固定的；

方三：

num = str(1234)

def rev(x):
     if x == -1:
         return ''
     return num[x] + rev(x-1)

print(rev(len(num)-1))

3、

def peach(days=10):
     if days == 1:
         return 1
     return (peach(days-1)+1) * 2

print(peach())

注：

这里必须是10，因为return (peach(days-1)+1)*2立即拿不到结果，必须通过再次进入函数时，判断是不是到了最后一天；即，当前使用的值是由下一次函数调用得到，所以要执行10次函数调用；

###############

def peach(days=1):   #days只用于计数
     if days == 10:
         return 1
     return (peach(days+1)+1) * 2

print(peach())