Py002-01-05递归

M02

递归

原理就是自己调用自己

1
2
3
4
5
6
7
8
def xx(n):
    print(n)
    xx(n+1)

xx(1)

# 报错  maximum recursion depth exceeded while calling a Python object
# 大概打印不到1000次 就报错了

每次调用函数都会将其压入栈中,栈有一定的限制，超过就会溢出了

就像步枪的「弹匣」是由容量限制的

阶乘 1 2 3 4 … n

1
2
3
4
5
6
def xxx(n):
    if n ==1:
        return 1
    return xxx(n-1)*n

print(xxx(4)) #　24

正确使用递归

  • 要有结束条件，否则就死循环了
  • 每次进入更深一层递归时，问题规模要比上一次有所减少
  • 递归效率不高

适用场景

  • 兔子数列—->斐波那契
  • 汉诺塔

递归的优化(尾递归)

  • 递归之所以效率低就是因为每执行一步就会压栈
  • 每次压栈的执行结果要保存 如 4的阶乘 需要知道 3阶乘的结果 。。。。
1
2
3
4
# 注意这个代码在python是不支持的会报错， 这样的代码实际就是尾递归。
def cal(n):
    print(n)
    return cal(n+1)