我有一个这样定义的函数:
F(n) = n
if n<=3
F(n) = F(n-1) + 2 * F(n-2) + 3 * F(n-3)
if n>3
现在,我已将其编写为递归函数,并且运行良好。 我试图将其编写为迭代函数,但我似乎无法实现它。
输出应该是,例如:
print(FRec(5)) => 22
print(FRec(10)) => 1657
print(FRec(15)) => 124905
有什么建议吗?
这是我的递归实现:
def FRec(n):
if(n <= 3):
return n
if(n > 3):
return FRec(n - 1) + 2 * FRec(n - 2) + 3 * FRec(n - 3)
最佳答案
您所需要的只是保留最后 3 个结果:
from collections import deque
def F_iter(n):
if n <= 3:
return n
prev = deque([1, 2, 3], maxlen=3)
for i in range(4, n + 1):
result = prev[-1] + 2 * prev[-2] + 3 * prev[-3]
prev.append(result)
return prev[-1]
如果双端队列
对您来说不“可用”,那么您可以用一些列表切片和串联来替换它,效率低下:
prev = [1, 2, 3]
for i in range(4, n + 1):
result = prev[-1] + 2 * prev[-2] + 3 * prev[-3]
prev = prev[1:] + [result]
演示:
>>> F_iter(5)
22
>>> F_iter(10)
1657
>>> F_iter(15)
124905
关于python - 此递归函数的迭代版本,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40549853/