Python:将此递归函数转换为迭代

Question

def g(n):
"""Return the value of G(n), computed recursively.

>>> g(1)
1
>>> g(2)
2
>>> g(3)
3
>>> g(4)
10
>>> g(5)
22
"""
if n<=3:
    return n
else:
    return g(n-1)+2*g(n-2)+3*g(n-3)

如何将其转换为迭代函数？到目前为止,我没有意识到编写递归函数有时比编写迭代函数更容易.之所以我认为这么难,是因为我不知道函数正在做什么操作.在递归中,并不是很明显发生了什么.

我想编写一个迭代定义,我知道我需要使用while循环,但是每次我尝试编写一个时,我都会向g_iter(n)添加额外的参数(当应该只有一个时),或者我做一个递归调用.有人至少可以让我走上正确的道路吗？您不必给我一个完整的解决方案.

仅供参考:我们还没有了解到我在所有这些页面上看到的那种常见的"堆栈".我宁愿远离这个.

def g_iter(n):
"""Return the value of G(n), computed iteratively.

>>> g_iter(1)
1
>>> g_iter(2)
2
>>> g_iter(3)
3
>>> g_iter(4)
10
>>> g_iter(5)
22
"""
"*** YOUR CODE HERE ***"

Answer 1

def g(n):
    if n <= 3:
        return n
    a, b, c = 1, 2, 3
    for i in range(n - 3):
        a, b, c = b, c, c + 2 * b + 3 * a
    return c

UPDATE对评论的响应,不使用for循环.

def g(n):
    if n <= 3:
        return n
    a, b, c = 1, 2, 3
    while n > 3:
        a, b, c = b, c, c + 2 * b + 3 * a
        n -= 1
    return c