Python性能优化：用循环替代递归计算斐波那契与杨辉三角

斐波那契数列：从递归到循环的优化

斐波那契数列

提到递归，大家脑海中浮现的经典案例往往就是斐波那契数列。

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

当然，为了确保程序的健壮性，我们需要引入 try...except...机制。

def fib(n):
  if isinstance(n, int):
    print('兄弟,输入正整数哈')
    return
  try:
    if n==1 or n==2:
      return 1
    elif n <= 0:
      print('兄弟别输入0或负数呀')
    else:
      return fib(n-1)+fib(n-2)
  except RecursionError:
    print('兄弟，超过了最大递归深度'

不可否认，无论是从时间复杂度还是空间复杂度的角度来看，递归方案的表现确实不尽如人意。以下是递归版本的代码实现：

def fib(n):
  if n==1 or n == 2:
    return 1
  a, b = 1, 1
  for i in range(2, n):
    a, b = b, a+b
  return b

这里简要说明三个关键点：

• 为什么使用 range(2, n) ？因为斐波那契数列通常从第1项开始计数，因此 fib(n) 对应的是数列的第 n 项。
• 由于前两项的值均为 1，我们需要跳过这两项，因此循环次数为 range(2, n) （即执行 n-2 次循环）。
• 在语句 a, b = b, a+b 中，可能存在一些疑惑。简要说明一下，Python解释器通常将逗号分隔的变量赋值视为一个元组操作。
• 同时，解释器会优先计算等式右侧的表达式，因此这实际上等同于元组拆包赋值的过程。
• 这句话的核心逻辑在于：在等式右侧，将当前的 b 值视为 fib(n-2)，而将 a+b 的结果视为 fib(n-1)。

杨辉三角：递归实现的局限性

杨辉三角

同样地，我们先写出递归版本的实现（此处暂不考虑边界特殊情况，主要关注核心逻辑）：

def YH_tri(a, b):
  if a == b or b == 0:
    return 1
  else:
    return YH_tri(a-1, b)+YH_tri(a-1, b-1)

大家可以先思考一下如何将其改写为循环形式。

总结

以上内容介绍了如何利用循环机制替代递归函数来提升Python的执行效率，希望能对大家有所帮助。如有任何疑问，欢迎留言，小编会及时回复。感谢大家对本站的支持！ 如果您觉得本文对您有帮助，欢迎转载，请注明出处，谢谢！