我试图用python为fibonacci序列制作一个递归函数

Question

函数应该返回fibonacci序列的前n个数字的列表，但它什么也不返回，我想知道为什么

def fibonacci(n, sequence=[0, 1], originalN=0):
print(n, sequence[:-2])
if n <= 0:
print(n)
return(sequence[:-2])
nextValue = sequence[-1] + sequence[-2]
sequence.append(nextValue)

fibonacci(n-1, sequence, originalN)
print(fibonacci(10))

主功能中的一些打印功能被留下来进行调试

Answer 1

您缺少一个return语句。递归调用不会返回递归堆栈上的切片。你的斐波那契数列甚至使用前面的代码构建的唯一原因是它们都共享同一个列表对象。

def fibonacci(n, sequence=[0, 1], originalN=0):
if n <= 0:
return (sequence[:-2])
nextValue = sequence[-1] + sequence[-2]
sequence.append(nextValue)
return fibonacci(n-1, sequence, originalN)
print(fibonacci(10))

输出：

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

编辑：为了澄清，您之前的return语句只返回了最深调用(递归树上的叶子到其父级(当n为1时(的序列，但递归调用也需要return语句才能将此值传递到递归树上。

您可以避免使用递归堆栈，并进行更高效的Fibonacci序列计算，如下所示：

def fibonacci(n):
sequence = [0, 1]
for i in range(2, n):
sequence.append(sequence[-1] + sequence[-2])
return sequence

编辑2：正如@Clockwork Muse建议的那样，一种更像蟒蛇的方法是使用无限生成器而不是返回列表。您也可以生成任意长度的序列。以下是我对这种方法的看法：

def fib():
a, b = 0, 1
while True:
yield a
a, b = b, a + b
sequence = fib()

Demo(n可以是任何东西，因为fib是一个生成器对象，并将继续生成序列中的下一个数字(：

n = 10
for i in range(n):
print(next(sequence), end=", ")

输出：0, 1, 1, 2, 3, 5, 8, 13, 21, 34,

Answer 2

这是由于缺少return语句，如果条件没有进入if块，那么它只是简单地调用递归函数，但不返回任何内容。它只在基本情况下返回。

def fibonacci(n, sequence=[0, 1], originalN=0):
#print(n, sequence[:-2])
if n <= 0:
#print(n)
return(sequence[:-2])
nextValue = sequence[-1] + sequence[-2]
sequence.append(nextValue)
return fibonacci(n-1, sequence, originalN)
print(fibonacci(10))