10.递归函数

递归函数

01.函数直接或间接调用自身的行为称为递归。

• 递归必须有边界条件，递归前进段，递归返回段。
  • 当边界条件不满足的时候，递归前进。
  • 当边界条件满足的时候，递归返回。
• 递归函数的注意事项：
  • 递归函数性能较差，不建议使用。
    • 对于一个给定n的函数，会进行2n次递归，深度越深，效率越低。
  • 递归函数有最大深度限制，其值为1000。
    • 递归函数的最大深度限制可以通过sys.getrecursionlimit()查看和修改。
    • 递归函数超过深度限制会抛出RecursionError错误。
    • 如果函数复杂，使用递归会导致函数反复压栈，容易造成内存溢出。
• 在函数中通过其他函数调用自身的行为称为间接递归。
  • 间接递归要避免形成循环递归。
• 递归函数的示例：

my_list = []

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

for i in range(1, 10):
    my_list.append(fib(i))
print(my_list)

• 递归函数的改进：

my_list = []

def fib(n, a=0, b=1):
    a, b = b, a+b
    if n == 0:
        return a
    return fib(n-1, a, b)

for i in range(5):
    my_list.append(fib(i))

• 上一次计算完的结果，直接作为实参传入下一次计算中。

02.递归函数的总结：

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