尾递归Fibonacci

Question

如何在O(n)中没有运行循环的情况下实现递归Fibonacci函数？

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作为结果.这非常适合你给出的"提示".

我希望你花时间比较这两种解决方案并说服自己相同.了解如何将迭代解决方案转换为等效的递归解决方案(反之亦然)是一项很好的开发技巧.