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

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]

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]
>

但是正如@TomKarze评论的那样，有更好的算法。但是因为你坚持递归地做这件事，效率并不是首要问题。