时间戳

首页 > 解决方案 > 使用递归的斐波那契数列

python - 使用递归的斐波那契数列

问题描述

我想创建一个函数来生成所谓的超级斐波那契数列，它是一个数字列表，从第三项开始，每个项都是前面所有项的总和。它需要 2 个参数：t2 和 n。t2 是列表中的第二项，n 是列表中的项数。例如。

superFibSeq(10,10) >>> [1,10,11,22,44,88,176,352,704,1408]
superFibSeq(4,10) >>> [1, 4, 5, 10, 20, 40, 80, 160, 320, 640]

我一直坚持这一点，不知道从哪里开始。如果我只想使用递归，我应该如何考虑。

标签： pythonrecursion

解决方案

上面有人说这个问题中的递归真的很奇怪。你想要递归，当然。

def f(t2, n):
    if n == 0:
       return []
    elif n == 1:
       return [1]
    elif n == 2:
        return [1, t2]
    else:
        temp = f(t2, n - 1)
        return temp + [sum(temp)]

这个算法是 O(n^2) 而不是 O(n)

推荐阅读