尾递归斐波那契 [英] Tail Recursion Fibonacci

问题描述

如何在O(n)中没有循环的情况下实现递归斐波那契函数?

How do I implement a recursive Fibonacci function with no loops running in O(n)?

推荐答案

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

Typically I'd be against posting an answer to a homework question like this, but everything posted so far seems to be overcomplicating things. As said in the comments above, you should just use recursion to solve the problem like you would do iteratively.

这是迭代解决方案:

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

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

Here's an equivalent recursive solution:

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 作为结果.这与您获得的提示"非常吻合.

Note that in both cases we actually compute up to F_n+1, but return F_n as the result. This fits nicely with the "hint" you were given.

我希望您能花些时间比较这两种解决方案，并让自己确信它们是等效的.了解如何将迭代解决方案转换为等效的递归解决方案(反之亦然)是一项很好的开发技能.

I hope that you'll take the time to compare the two solutions and convince yourself that they're equivalent. Understanding how to transform an iterative solution to an equivalent recursive one (or vice versa) is a good skill to develop.

这篇关于尾递归斐波那契的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！