编写一个递归函数来解决斐波那契数列。

Question

我想在Python中编写一个递归函数来计算斐波那契数列。

x将是起始点，y将是x的后续项，l是长度。

我不明白我的思路错误在哪：

 def fib(x, y, l, fibList=None):
    fibList = []
    z = x + y
    x = y
    fibList.append(z)
    y = z

    if len(fibList) <= l:
        return fib(x, y, l, fibList)
    else:
        return(fibList)

结果如下：

RecursionError: maximum recursion depth exceeded while calling a Python object

我可以用循环解决它，但不能用递归函数。

- TheDev

---

为了确认变量x、y、l和fibList的值是否符合预期，建议在进入函数时将它们打印出来。请注意不改变原意，使翻译易于理解。 - jarmod

你可以阅读这个网址：https://www.programiz.com/python-programming/recursion，该页面有递归函数中发生的事情的可视化解释。 - minion

我的意思是有人给了你一个解决方案，但问题是，在每个fib函数调用的开头，你会清除你的fibList...所以列表的长度始终<= 1，因此你会陷入无限递归循环中，这不是好的。像“if fibList == None: ...”这样添加一些内容。 请注意，这里涉及到代码和上下文，所以我的回答可能并不完全准确或适用于所有情况。 - Raqha

请注意，即使使用其他答案提出的修复方法，您的代码也无法给出完全正确的结果。斐波那契数列以一个 0 项开始，然后是两个 1 项。没有办法调用您的函数以产生前两个项。例如，要获得零，唯一的方法是将 x 和 y 都传入 0，这当然不会导致序列中每个项的正确生成。请参阅我的答案，它解决了这个问题以及无限递归问题，并为您的函数提供了一个模块，使其更易于调用。 - CryptoFool

Answer 1

这里有一些问题。一旦你解决了无限递归的问题，你仍然有一个问题。

正如@Raqha所指出的那样，你需要在fib函数被调用时不每次都初始化你的列表，而是只有第一次，当fibList参数没有被提供并且默认为None时。

你的代码不能生成序列中的前两个数字0和1。你可以通过简单地初始化列表以包括这些项，并调整逻辑来仅提供N-2个更多的术语来修复这个问题。

你的函数签名可以改进，使调用者更容易使用它。调用者只关心他/她想要的术语数。用户不应该知道要输入哪些初始x和y值。

这是你的代码版本，修复了无限递归的问题，缺少术语的问题，并且将签名重新排列，以便用户可以简单明了地调用函数：

def fib(l, x=0, y=1, fibList=None):
    if fibList is None:
        fibList = [0, 1]
    z = x + y
    x = y
    fibList.append(z)
    y = z

    if len(fibList) < l-1:
        return fib(l, x, y, fibList)
    else:
        return(fibList)

print(fib(10))

结果：

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

- CryptoFool

Answer 2

在第二行中，您设置了fibList = []。这意味着每次您递归调用函数时，它都会将列表重置为空，因此len(fibList)始终等于1。

删除该行，以便不重置fibList变量，然后它应该正确地达到退出条件。现在它的写法是无限运行直到崩溃。

- akerr

Answer 3

在每次调用fib函数的开始，您可以使用fibList = []清除fibList。 因此，该列表的长度始终为<= 1，因此会遇到无限递归循环，这是不好的。 您需要添加类似if fibList is None:的内容。

当第一次调用函数“fib”而没有在参数列表中提供任何第四个语句时，“fibList”的值将最初设置为“None”。 但是稍后当您再次递归调用函数“fib”时，您会在参数列表中提供一个fibList。 因此，该值不再是“None”。 所以当添加如上所述的if语句时，函数知道您是从外部调用函数（当您在代码中调用它作为“fib（1,2,10）”时），还是当函数递归调用自身时。 因此，您不必每次调用函数时重置fibList，而只需在开始时设置一次即可。

def fib(x, y, l, fibList=None):
    if fibList is None:
        fibList = []
    z = x + y
    ...

- Raqha

---

如果fibList等于None，它做什么呢？ 如果fibList是None，它会创建一个新的空列表，否则它会将内容追加到列表中，对吗？ - TheDev

如果fibList尚未初始化，则会初始化它--> fibList = []。然后，您将新的fib附加到此列表中，在下一个if语句中查找其长度。在第一次迭代中，长度为1，当l变量大于1时，您将再次调用此函数，但这次使用给定的fibList，因此您的fib列表不再为None，因此if语句为false，它不会重置您的fibList。知道列表的长度可以增长，直到达到l变量，然后第二个if语句为false，因此您返回fiblist。 - Raqha

@Raqha，你应该把这个注释放在你的答案上面。这是好东西。 - CryptoFool