跳转至

12. 递归

递归函数 recursion

递归是指:函数直接或间接调用自身

递归示例

    # 函数直接调用自身
    def f():
        f()  # 直接调用自身

    f()
    print('递归完成')

    #函数间接调用自身
    def fa():
        fb()
    def fb()
        fa()
    fa()
    print('递归完成')

递归说明

  • 递归一定要控制递归的层数,当符合某一条件时要终止递归调用
  • 几乎所有的递归都能用while循环来代替

递归的优缺点

  • 优点: 可以把问题简单化,让思路理会为清晰,代码更简洁
  • 缺点: 递归因系统环境影响大,当递归深度太大时,可能会得到不可预知的结果

递归调用分为两个阶段

  • 递推阶段: 从原问题出发,按递归公式递推,从未知到已知,最终达到递归终止条件
  • 回归阶段: 按递归终止条件求出结果,逆向逐步代入递归公式,回归到原问题求解
# 限制递归层数的示例
def fx(n):
    print('递归进入第 %d 层' % n)
    if n == 3:
        return
    fx(n + 1)
    print('递归退出第 %d 层' % n)

fx(1)
print('程序结束')

递归求阶乘示例

# 给出一个数n ,写一个函数myfac(n)来计算n!
#   n! =1*2*3*4*5*...*n
#   print(myfac(5))  # 120
def myfac(n):
    # 用递归来实现
    if n == 1:
        return 1
    # 如果不是1,则递推到下一级求解
    return n * myfac(n-1)

print(myfac(6))

练习

用递归实现求和
        def mysum(n):
            # 返回1 + 2 + 3 + 4 + 5...+ n的和

        print(mysum(100))  # 5050