python - 尾递归斐波那契

Question

如何在 O(n) 中实现没有循环运行的递归斐波那契函数？

Answer 1

通常我会反对发布这样的家庭作业问题的答案，但到目前为止发布的所有内容似乎都过于复杂了。如上面的评论所述，您应该像迭代一样使用递归来解决问题。

这是迭代解决方案:

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

这是一个等效的递归解决方案:

def fib(n):
  def fib_help(a, b, n):
    return fib_help(b, a+b, n-1) if n > 0 else a
  return fib_help(0, 1, n)

请注意，在这两种情况下，我们实际上计算了 F_n+1，但返回 F_n 作为结果。这与您收到的“提示”非常吻合。

我希望您能花时间比较这两个解决方案并说服自己它们是等价的。了解如何将迭代解决方案转换为等效的递归解决方案(反之亦然)是一项需要培养的好技能。