计算至少 n 个斐波那契数列

Question

我正在尝试制作一个允许用户输入数字的函数，结果将是一个包含斐波那契数列的列表，如果输入不在系列中，则包含最多输入的斐波那契数列。例如，输入 4 将 return [0, 1, 1, 2, 3, 5] 但输入 3 将 return [0, 1, 1, 2, 3]。我已经设法使用以下功能做到了这一点：

    def fibonacci(n):
        series = [0]
        if (n == 0):
            pass
        else:
            series.append(1)
            if (n == 1):
                pass
            else:
                while(series[len(series)-1] < n):
                    newValue = series[len(series)-1] + series[len(series)-2]
                    series.append(newValue)
        print(series)

但是，我现在希望能够递归地执行此操作，有什么想法吗？

Answer 1

可能的解决方案如下

def fibo_up_to(n):
    if n < 2:
        return [1,1]
    else:
        L = fibo_up_to(n-1)
        if L[-1] < n:
            L.append(L[-1] + L[-2])
        return L

想法是，对于 return 所有小于 n 的斐波那契数列，您可以请求小于 n-1 的列，然后可能只添加一个元素.如果我们将前两个数字定义为 [1, 1]，这从 2 开始起作用。使用 [0, 1] 而不是 2 会产生问题，因为单个下一个元素是不够的。

这段代码在时间上并没有低效（斐波那契是一个双重递归，这是一个简单的递归），但是使用了很多堆栈space。

Answer 2

 def calculate_fibonnaci(n):
     if n == 0:
         return 0
     if n == 1:
         return 1
     else:
         return calculate_fibonnaci(n - 1) + calculate_fibonnaci(n - 2)

这是一个使用递归函数的简单解决方案。

计算至少 n 个斐波那契数列

Calculate Fibonacci numbers up to at least n

python

recursion

list

fibonacci