函数之 递归函数

def fact(n): 
    if n == 1:
        return 1
    else: 
        return n * fact(n-1)
print(fact(1))
# print(fact(2))
# print(fact(10))
# print(fact(100))
# print(fact(900))
# print(fact(1000)) # 报错  递归栈溢出
# 解决递归调用栈溢出的方法是通过尾递归优化，事实上尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。

# 尾递归是指，在函数返回的时候，调用自身本身，并且，return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。

小结

使用递归函数的优点是逻辑简单清晰，缺点是过深的调用会导致栈溢出。
针对尾递归优化的语言可以通过尾递归防止栈溢出。尾递归事实上和循环是等价的，没有循环语句的编程语言只能通过尾递归实现循环。
Python标准的解释器没有针对尾递归做优化，任何递归函数都存在栈溢出的问题。

练习

汉诺塔的移动可以用递归函数非常简单地实现。

B=[] #设置操作过程列表
def move(n, a, b, c):
    global s
    if n==1:
        buzhou=a+str(n)+'-->'+c+str(n) #一个圆盘需要从A到C操作步骤
        B.append(buzhou) #向列表中添加操作步骤
        return
    move(n-1,a,c,b) # 将A柱的n-1个盘移到B柱
    buzhou=a+str(n)+'-->'+c+str(n) #将A柱的第n个盘移到C柱操作步骤
    B.append(buzhou) #向列表中添加操作步骤
    move(1,a,b,c) #将A柱上最后一个盘移到C柱=
    move(n-1,b,a,c) #将过渡柱子B上n-1个圆盘B移动到目标柱子C
    
move(3,'A','B','C') #2**64-1，64次太大，这里用6个盘子
print('共需操作'+str(len(B))+'次','操作过程为',B)#计算6个盘子的步骤数及操作过程

关注一波！喜欢一波！本人是前端菜鸟，正在做自己的个人博客邓鹏的博客，欢迎来交流学习， 使用的技术 vue + koa2 + mysql + php + nginx！