Python递归函数函数执行流程

要明白递归首先需要明白函数的执行流程。

比如下面的这段程序。

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

结果为：
main called
foo1 called 100 101
foo3 called 200
foo2 called 200
main ending

上面的代码执行流程为：

首先在全局帧中生成foo1、foo2、foo3、main函数对象。
然后main函数调用。
main函数中查找内建函数print压栈，然后将常量字符串压栈，然后调用函数，弹出栈顶。
main函数中全局查找函数foo1压栈，然后将常量100,101压栈，调用函数foo1，创建栈帧。然后字符串和变量b,b1压栈，调用函数，弹出栈顶，返回值。
main函数中全局查找函数foo2函数压栈，然后将常量200压栈，调用foo2，创建栈帧。foo3函数压栈，变量c引用压栈，调用foo3，创建栈帧。foo3完成print函数调用后返回。foo2恢复调用，执行print后，返回值。main中foo2调用结束弹出栈顶，main继续执行print函数调用，弹出栈顶，main函数返回。

递归

所谓的递归也就是函数直接或者间接调用自身。需要注意的是递归一定要有边界条件（不然就就是死循环），递归前进段、递归返回段，当边界条件不满足的时候，递归前进，而当递归条件满足的时候，递归返回。

递归相比于循环，只是让解决方案更加清晰，并没有性能上的优势。在有些情况下，如果使用循环，程序的性能可能会更高，而如果使用递归的话，程序可能更容易理解。

比如要生成一个斐波拉契数列，1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... ߧ如果设f(n)为该数列的第n项，那么可以推导出这样的公式：f(n)=f(n-1)+f(n-2).

使用循环，生成斐波拉契数列，代码为：

pre = 0
cur = 1#第一个
print(pre,cur,end=" ")
n = 4
for i in range(n-1):
    pre,cur = cur,pre+cur
    print(cur,end = " ")

结果为：

0 1 1 2 3 

将它抽象出函数：

def fib(n):
    pre = 0
    cur = 1
    print(cur,end=" ")
    for i in range(n-1):
        pre,cur = cur,pre+cur
        print(cur,end = " ")
fib(10)

结果为：

1 1 2 3 5 8 13 21 34 55

而如果使用递归的话，代码可以很简洁：

#第n项的数字为：

def fib(n):
    if n<2:
        return 1
    else:
        return fib(n-1)+fib(n-2)
fib(10)

上面的代码可以简化为：
def fib(n):
    return 1 if n<2 else fib(n-1)+fib(n-2)
fib(10)

而生成数列的代码为：

def fib(n):
    return 1 if n <2 else fib(n-1) + fib(n-2)

print(fib(10))

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

结果为：
89
1 1 2 3 5 8 13 21 34 55 89

由上面的例子可以看到，递归一定要有退出条件，而递归调用一定会执行到这个退出条件，如果没有退出条件的递归调用，就是无限调用，会陷入无限循环，而且递归调用的深度不宜过深，Python对递归调用的深度做了限制（1000）以保护解释器，超过递归深度的限制，会抛出recursionerror错误，同时可以使用sys.getrecursionlimil()设置递归的深度。

递归的性能

循环稍微复杂一些，但是只要不是死循环，就可以多次迭代算出结果，递归函数的代码极简易懂，但是只能获取到最外层的函数调用，内部的递归结果都是中间结果，而且给定一个N都要进行近2N次递归，深度越深，效率就会越低，为了获取斐波拉契数列需要再在外面套一个n的循环，效率就更低了。如果递归复杂，函数会反复的压栈，这样栈的内存很快就会溢出。所以会有递归深度限制。如下面的代码：

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)

结果为：

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 0.001

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)

结果为：

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 9.371536

上面的例子可以看到for循环，只需要0.01秒就可以很快算出35个斐波拉契数列，而递归的话则需要9秒多。效率特别低，这个时候有什么可以改进的吗？

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

结果为：

0 1 1 2 3 5 8 13 21 34 55

上面的这个递归函数就和循环的思想很类似了，参数n是边界条件，用n来计数，上一次的计算结果直接用作函数的实参，这样的话，效率更高，和循环相比较的话，性能更近。

所以递归并不一样都是效率低下，但是它有深度限制。

可以对比下三个斐波拉契数列生成函数的效率。如下：

import datetime
# Fib Seq
start = datetime.datetime.now()
pre = 0
cur = 1 # No1
print(pre, cur, end=' ')
n = 35
# loop
for i in range(n-1):
    pre, cur = cur, pre + cur
    print(cur, end=' ')
delta = (datetime.datetime.now() - start).total_seconds()
print(delta)


# Fib Seq
start = datetime.datetime.now()
pre = 0
cur = 1 # No1
print(pre, cur, end=' ')
# recursion
def fib1(n, pre=0,cur=1):
    pre, cur = cur, pre + cur
    print(cur, end=' ')
    if n == 2:
        return
    fib1(n-1, pre, cur)

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


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

for i in range(n):
    print(fib2(i), end=' ')
delta = (datetime.datetime.now() - start).total_seconds()
print(delta)

前面两个性能相当，而第三个效率特特别低下。写递归应该尽量避免写成第三个这样的。

间接递归

所谓的间接递归，就是通过别的函数间接调用了函数自身，但是，如果构成了循环递归调用就是件非常危险的事情，而且这种情况在代码复杂的情况下，很还可能发生。所以一定要规范代码，来避免发生这种调用的发生。比如下面这个例子。

def foo1():
    foo2()
def foo2():
    foo1()
foo1()

上面的代码就会陷入死循环。应该尽量的避免。

递归总结：

递归是一种很自然的表达，符合逻辑思维。
递归相对来讲运行效率低，每一次调用函数都要开辟栈帧。
递归有深度限制，如果递归的层次太深，函数反复的压栈，栈内存很快就会溢出。
如果是有限次的递归，可以使用递归调用，或者使用循环代码，循环代码稍微复杂一些，但是只要不是死循环，可以多次迭代直至算出结果。
绝大多数递归，都可以使用循环来实现。
即便递归代码简洁，但是能不用则不用递归。

练习题：

求n的阶乘！
将一个数逆序放入列表中，比如1234--[4,3,2,1]
解决猴子吃桃问题：猴子第一天摘下若干个桃子，马上吃了一半，还不过瘾，又多吃了一个，第二天早上又将剩下的桃子吃掉了一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想吃的时候，只剩下一个桃子，求第一天共摘了多少个桃子。

#求阶乘
def fac(n):#性能最好
    if n==1:
        return 1
    else:
        return n*fac(n-1)
fac(10)

结果为：

3628800

def fac1(n,p=1):
    if n==1:
        return p
    p*= n
    print(p)
    fac1(n-1,p)
    return p

fac1(10)

结果为：

10
90
720
5040
30240
151200
604800
1814400
3628800
10

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[0]
fac2(10)

结果为：
3628800

def fac3(n,p=1):
    p*=n
    if n==1:
        return p
    else:
        return fac4(n-1,p)

fac3(10)

结果为：
3628800

2.将一个数逆序放入列表中

data = str(1234)

def revert(x):
    if x==-1:
        return " "
    return data[x]+revert(x-1)

print(revert(len(data)-1))

结果为：
4321 

def revert1(n,lst = None):
    if lst is None:
        lst = []
        
    lst.append(n%10)
    if n//10 ==0:
        return lst
    return revert1(n//10,lst)
revert1(12345)

结果为：

[5, 4, 3, 2, 1]

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

revert2(12345)

结果为：
[5, 4, 3, 2, 1]

num = 12354

def revert3(num,target=[]):
    if num:
        target.append(num[len(num)-1])#target.append(num[-1:])
        revert3(num[:len(num)-1])
    return target
print(revert3(str(num)))

结果为：
['4', '5', '3', '2', '1']

猴子吃桃问题：

def peach(day= 9,sum = 1):
    sum=2*(sum+1)
    day-=1
    if day ==0:
        return sum
    return peach(day,sum)
print(peach())

结果为：
1534

def monkey(n):
    if n==1:
        return 1
    return 2*monkey(n-1)+2
monkey(10)

结果为：
1534

这个猴子吃桃的问题，可以假设猴子摘了x个桃子

d1: x//2-1

d2:d1//2-1

d3:d2//2-1

……

d9:d8//2-1

d10:1

那么：

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

结果为：
1534

应该注意的是，这里必须是10，因为return (peach(day-1)+1)*2立即拿不到结果，必须通过再一次进入函数时判断是不是到了最后一天。也就是当前使用的值是由下一次函数调用得到的，所以要执行10次函数调用。换一种方式表达：

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

结果为：
1534

Python递归函数 函数执行流程

递归

递归的性能

间接递归

相关推荐

Python递归函数函数执行流程