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

另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。