python - 此递归函数的迭代版本

标签 python recursion iteration

我有一个这样定义的函数:

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/

相关文章:

vba - 在 VBA 中识别 For Each 循环的迭代?

arrays - 如何迭代多个 Perl 数组

python - 使用 Nodejs 中的前端和 Python 中的后端服务器运行 Google App Engine 的一个实例

python/numpy 一次合并 4 行子数组

java - LeetCode 中的递归和回溯是如何工作的?

ruby - 以*干净*的方式在 Ruby 中实现非常深的递归的正确方法是什么?

java - 通过遍历枚举来分配参数

Python:用元组值更新字典键

Python/PostgreSQL 插入行无效

python - 使用递归函数将嵌套列表转换为集合