Python 尾递归斐波那契
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/22111252/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Tail Recursion Fibonacci
提问by Mat.S
How do I implement a recursive Fibonacci function with no loops running in O(n)?
如何在 O(n) 中实现没有循环的递归斐波那契函数？
采纳答案by DaoWen
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.
通常我会反对像这样发布家庭作业问题的答案，但到目前为止发布的所有内容似乎都过于复杂。正如上面的评论中所说，您应该像迭代一样使用递归来解决问题。
Here's the iterative solution:
这是迭代解决方案：
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)
Note that in both cases we actually compute up to Fn+1, but return Fnas the result. This fits nicely with the "hint" you were given.
请注意，在这两种情况下，我们实际上最多计算 F n+1，但返回 F n作为结果。这与您得到的“提示”非常吻合。
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.
我希望您花时间比较这两种解决方案并说服自己它们是等效的。了解如何将迭代解决方案转换为等效的递归解决方案（反之亦然）是一项很好的发展技能。
回答by 831
To solve this in linear time, you must use a dynamic programming technique known as memoization.
要在线性时间内解决这个问题，您必须使用称为记忆化的动态编程技术。
The algorithm for Fibonacci in pseudo-code, using memoization, looks like this:
使用记忆化的伪代码斐波那契算法如下所示：
memoryMap[n]
func fib(int n)
if (n is in memoryMap) then
return memoryMap[n]
if (n <= 1) then
memoryMap[n] = n
else
memoryMap[n] = fib(n-1) + fib(n-2)
return memoryMap[n]
To explain, you after each call to fib(x) you be storing the result in a memory map. For each subsequent call, all lookups to fib(x) will be free: that is, looking up the result in the memory costs only O(1) time.
解释一下，每次调用 fib(x) 后，您都将结果存储在内存映射中。对于随后的每次调用，对 fib(x) 的所有查找都是免费的：也就是说，在内存中查找结果只需 O(1) 时间。
回答by Deepak Kumar
Scala code for finding nth Fibonacci Number. For more information on Tail Recursion http://nerds.logdown.com/posts/1406258-n-th-fibonacci-number
用于查找第 n 个斐波那契数的 Scala 代码。有关尾递归的更多信息http://nerds.logdown.com/posts/1406258-n-th-fibonacci-number
object Main {
def main(args: Array[String]) {
println(fib(9));
println(fib(8));
println(fib(7));
println(fib(6));
println(fib(5));
println(fib(4));
println(fib(3));
println(fib(2));
println(fib(1));
println(fib(0));
}
def fib(n: Int): Int = {
def fib(n: Int, p :Int, c: Int): Int ={
if (n == 0) return -1; // undefined
if (n == 1) return p;
fib(n-1, c, p + c)
}
fib(n, 0, 1);
}
}
回答by bcherny
In case someone is looking for a JavaScript solution:
如果有人正在寻找 JavaScript 解决方案：
function _fib(n, left, right) {
switch (n) {
case 0: return 0
case 1: return right
default: return _fib(n - 1, right, left + right)
}
}
function fib(n) {
return _fib(n, 0, 1)
}
That runs in O(n) time and O(1) space with tail call optimization.
它在 O(n) 时间和 O(1) 空间中运行，并带有尾调用优化。
