Python中递归函数的斐波那契级数

Question

您好，我正在尝试使用python中的递归函数生成斐波那契级数

这是我的密码

def fibolist(n):
    list1 = [1, 1]
    if n in (1,2) :
        return list1
    else:
        fibolist(n-1).append(sum(fibolist(n-1)[n-3:]))
        return list1

但当我输入任何数字作为参数时，结果是[1, 1] 你能帮帮我吗

Answer 1

只是为了修复您的代码：

def fibolist(n):
    if n in (0,1) :
        return [1,1]
    else:
        return fibolist(n-1)+[sum(fibolist(n-1)[n-2:])]

几点注意：

python中的列表的起始索引为0，因此最好从它开始（除非您想将起始返回设置为[0,1,1]以获得n in (1,2)）

另外，正如前面提到的，您不应该返回局部变量，因为您在每次go中都预先分配了该变量

Answer 2

你从

list1 = [1, 1]

您永远不会更改该值，然后将其返回到调用例程

对fibolist的每次调用都有一个名为list1的局部变量；追加到一并不改变调用程序中的list1值。您需要明确地这样做。试一试

else:
    return fibolist(n-1) + [sum(fibolist(n-1)[n-3:])]

Answer 3

您的代码没有更新从递归返回的list1变量。执行fibolist(n-1).append(...)更新下一级返回的列表，但这是一个单独的列表，因此list1不受影响

通过将最后两个值传递给函数本身，也可以使函数更简单：

def fibo(n,a=1,b=1): return [a] if n==1 else [a] + fibo(n-1,b,a+b)

顺便说一句，斐波那契序列的现代解释是从0,1开始的，而不是从1,1开始的，因此上面的签名应该是def fibo(n,a=0,b=1)

输出：

print(fibo(5))
#[1, 1, 2, 3, 5]