编写递归函数来求解斐波那契数列

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我可以用 for 循环来解决它，但不能用递归函数来解决。

Answer 1

这里有一些问题。一旦修复了无限递归，问题仍然存在。

您不需要每次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]

Answer 2

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

删除该行，以便 fibList 变量不会重置，然后它应该正确满足您的退出条件。现在是这样写的，它会永远运行，直到损坏为止。

Answer 3

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

当您首次调用函数“fib”而未在参数列表中提供任何第四条语句时，fibList 的值最初将设置为“None”。但稍后，当您再次递归调用函数“fib”时，您将在参数列表中提供一个 fibList。所以该值不再是“无”。因此，当添加如上所述的 if 语句时，该函数知道您何时从外部调用该函数（当您在代码中将其调用为“fib(1,2,10)”时），或者何时该函数递归地调用自身。因此，您不必每次调用该函数时都重置 fibList，而是在开始时仅设置 1 次。

def fib(x, y, l, fibList=None):

    if fibList is None:

        fibList = []

    z = x + y

    ...