我试图使用递归来解决所谓的tribonacci序列问题

Question

函数应该像 特里波那契([1， 1， 1]， 10(-> [1， 1， 1， 3， 5， 9， 17， 31， 57， 105]

这是我的代码

def tribonacci(signature, n):
if n <= 3:
return signature[:3]
else:
return tribonacci(signature, n-1).append(sum(tribonacci(signature, n-1)[-3:]))

它给了我一个属性错误："NoneType"对象没有属性"append"。

我真的不知道问题出在哪里。有人可以详细告诉我递归的工作原理吗？

Answer 1

正如@JonClements注释中已经指出的那样，append方法不返回列表。它返回None，因此调用者在尝试将该None用作列表时会遇到异常。

作为旁注，进行两次相同的递归调用是低效的。这将使您的程序第二次执行所有相同的工作。

因此，要解决这两个问题，只需逐步完成，如下所示：

def tribonacci(signature, n):
if n <= 3:
return signature[:3]
else:
result = tribonacci(signature, n-1)
result.append(sum(result[-3:]))
return result

这有效，但看起来仍然有点可疑，因为result列表在每个递归级别中都会发生突变。这意味着从理论上讲，所有这些执行上下文都会在递归树的更高级别看到稍后完成的突变。在这个特定的代码中，这不是问题，但人们可能会认为不改变列表更安全，而是返回一个新列表：

def tribonacci(signature, n):
if n <= 3:
return signature[:3]
else:
result = tribonacci(signature, n-1)
return result + [sum(result[-3:])]
print(tribonacci([1,1,1], 10))

如果要多次调用此函数，对n使用不同的值(但签名相同(，如果您实现记忆，则可以提高效率，以便可以重用早期的结果。