Python中Fibonacci序列的一个转折

Question

我在Python中学习递归，现在我遇到了这个练习的问题：

请记住，Fibonacci序列是一个数列，其中每个数都是前两个数的和。 对于这个问题，递归地实现Fibonacci，有一个转折！假设我们想要创建一个名为Fibonacci-3的新的数字序列。在Fibonacci-3中，序列中的每一个数都是前三个数的和。序列从三个1s开始，第四个斐波那契-3数是3 (1+1+1)，第五个是5 (1+1+3)，第六个是9 (1+3+5)，第七个是17 (3+5+9)，等等。 将函数命名为fib3，并确保使用递归。 下面的行将测试您的代码。 如果您的函数正确，它们将打印1、3、17和57。 打印(fib3(3))打印(fib3(4))打印(fib3(7))打印(fib3(9))

这是到目前为止的代码：

def fib3(n):
    if n <= 1:
        return n
    else:
        return(fib3(n-1) + fib3(n-2) + fib3(n-3))

但结果是: 1，2，11，37

你能帮我改正一下吗？

Answer 1

您的问题描述告诉您原因：

序列将从三个1s开始

但是，您的解决方案只返回用于1或更低版本的n == 1：

if n <= 1:
    return n

这意味着对于n == 2 (它仍然应该返回1)，您将返回fib3(2-1) + fib3(2-2) + fib3(2-3)，或者fib3(1) + fib3(0) + fib(-1)，这要归功于上面的测试，然后底层生成1 + 0 + -1 == 0。

对于n == 3，您将返回fib3(2) + fib3(1) + fib3(0)；我们在上面计算出fib3(2)是0，所以最终结果是0 + 1 + 0是您观察到的1。

最后，第4 fib3数(n == 4)，不返回3，而是fib3(3) + fib3(2) + fib3(1) == 1 + 0 + 1 == 2。

更改第一个测试返回的1 for n <= 3，以修复本系列中的前3个值：

def fib3(n):
    if n <= 3:
        return 1
    else:
        return fib3(n-1) + fib3(n-2) + fib3(n-3)

现在，代码通过了给定的测试：

>>> def fib3(n):
...     if n <= 3:
...         return 1
...     else:
...         return fib3(n-1) + fib3(n-2) + fib3(n-3)
...
>>> print(fib3(3))
1
>>> print(fib3(4))
3
>>> print(fib3(7))
17
>>> print(fib3(9))
57

Answer 2

如果是n <= 1，情况要比return n复杂一些。

以n = 4为例:您的递归调用将是fib(3)、fib(2)和fib(1)。

最后面的部分立即返回1，这就是您想要的。然而，这两个递归调用做了一些奇怪的事情。fib(2)递归到fib(1)、fib(0)和fib(-1)中，返回值基本上是返回一个很大的fat 0。fib(3)递归到fib(2) (我们看到的是0)、fib(1) (它工作，并且是1)和fib(0) (也是0)。

因此，从一开始就得到了1，从fib(3)的递归fib(3)组件中得到了1。这是你的2！

基本上，你想确保你的大小写不能返回一个负数。修复它(返回1或0)，您应该会很好。作为马蒂恩·皮特斯，您也可以使您的大小写n <= 3，并且它应该达到同样的效果。

Answer 3

让我给出最理想的“琵琶”答案。

要点是避免递归函数调用，以优化代码的效率。Pythonic的思维方式将涉及以下紧凑的代码，这是n个数的Fibonacci序列的迭代创建，包括种子数1、1、1。

def fibonacci_sequence(n):
    x = [1, 1, 1]
    [x.append(x[-1] + x[-2] + x[-3]) for i in range(n - len(x))]
    return x

import time
n = int(raw_input("Enter the size of Fibonacci-3 sequence: "))
start_time = time.time()
print fibonacci_sequence(n)
print "The time to compute the Fibonacci-3 sequence is: %s" % (time.time() - start_time)