python - 使用递归返回斐波那契序列列表的正确方法

Question

我了解如何使用迭代方法以及动态编程方法返回斐波那契数列。

通过递归，我理解了斐波那契的递归树。以及如何返回第 N 个斐波那契数

def fib(num):
    if num <= 2: 
        return num 

    return fib(num -1) + fib(num-2)

print(fib(5))

上面的代码返回8很棒，但我想了解如何通过更新上面的递归代码来返回序列列表。

eg: [1,1,2,3,5,8]

标签： pythonrecursionfibonacci

Answer 1

使用以 0 开头的斐波那契数列，我们可以递归地重写您的代码，无需任何外部数据，方法是：

def fib(index):
    if index <= 2:
        return [0, 1][:index]

    sequence = fib(index - 1)

    sequence.append(sum(sequence[-2:]))

    return sequence

print(fib(11))

输出

> python3 test.py
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
>

但正如@TomKarzes 评论的那样，有更好的算法。但是由于您坚持以递归方式执行此操作，因此效率不是主要问题。