计算斐波那契数至少为n [英] Calculate Fibonacci numbers up to at least n

问题描述

我正在尝试创建一个允许用户输入数字的函数，结果将是一个包含直到输入为止的斐波那契数字的列表，如果输入不在序列中，则该列表将包含一个以上的数字.例如，输入 4 将返回 [0、1、1、2、3、5] ，但是输入 3 将返回> [0，1，1，2，3] .我已经使用下面的功能做到了这一点:

I am trying to make a function that allows a user to input a number and the result will be a list containing Fibonacci numbers up to the input and one above if the input is not in the series. For example, input of 4 will return [0, 1, 1, 2, 3, 5] but input of 3 would return [0, 1, 1, 2, 3]. I have managed to do this using the function below :

    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)

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

However, I would now like to be able to do this recursively, any ideas?

推荐答案

以下是可能的解决方法

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

这个想法是要返回所有小于 n 的斐波那契数字的列表，您可以要求小于 n-1 的那些斐波那契数字的列表，然后可能只添加一个元素.如果我们将前两个数字定义为 [1，1] ，则从2开始有效.相反，使用 [0，1] 会造成2的问题，因为单个下一个元素是不够的.

the idea is that to return the list of all fibonacci numbers less than n you can ask for the list of those less than n-1 and then possibly add just one element. This works from 2 on if we define the first two numbers being [1, 1]. Using [0, 1] instead creates a problem for 2 because a single next element is not enough.

这段代码的时间效率不是很高(fibonacci是两次递归，这是一个简单的递归)，但是会占用大量堆栈空间.

This code is not inefficient on time (fibonacci is a double recursion, this is a simple recursion), but uses a lot of stack space.

这篇关于计算斐波那契数至少为n的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！