如何迭代地编写这个递归函数？

Question

在Python中：

def g(n):  
    if n <=3:        
        return n   
    return g(n-1) + 2 * g(n-2) + 3 * g(n-3)

我知道这个函数在做什么，但我似乎不知道如何使它迭代。请帮帮我。如果可能的话，请给我一个解释，以便我能完全理解这个问题。在

Answer 1

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

Answer 2

递归函数可以理解为

To find the value of g(30), find the value of g(29), g(28), and g(27)
  To find the value of g(29), find the value of g(28), g(27), and g(26)
    To find the value of g(28), find the value of g(27), g(26), and g(25)
      ...
        (repeat until all sub-finds have completed)

迭代函数从另一端开始

^{pr2}$

Answer 3

这看起来类似于fibonacci级数问题，以迭代的方式实现是非常重要的。它看起来也像是家庭作业，所以我会把fibonacci迭代的步骤贴出来，你应该能够把它应用到你的问题上。在

如果你不知道，斐波那契的定义如下：

def fib(n):
    if n <= 1:  # technically, this is not 100% correct, but it's fine for n>=0
        return n
    return fib(n-1) + fib(n-2)

我们来分析一下fib(n)。首先我们看到有两种不同的情况：n <= 1和{}。对于n <= 1，fib(n)没有依赖关系，因此我们可以计算：

^{pr2}$

现在我们要处理另一个案子。让我们首先做一个依赖性分析。对于fib(n)和{}，我们需要什么？我们调用fib(n-1)和{}。在迭代语言中，这是前面的两个值。所以很明显，我们需要跟踪这些。我们将从这一点上的两个小案例开始：

def fib_iter(n):
    if n <= 1:
        return n
    prev1, prev2 = 0, 1

我希望这是显而易见的。然后我们按照递归方法中解析函数的顺序来解析它们。当展开递归并分析函数时，我们发现第一个要计算的非trival值当然是fib(2)。然后fib(3)依此类推，直到到达n。由于递归方法，多个值需要多次求值，但在迭代方法中不需要这样做。将这些值相加，得到以下代码：

def fib_iter(n):
    if n <= 1:
        return n
    prev1, prev2 = 0, 1
    for i in xrange(2, n+1):
        curr = prev1 + prev2        # calculate fib(i)
        prev1, prev2 = prev2, curr  # shift previous value cache

唯一缺少的是返回值，在循环结束时它只是curr。正如我们预先检查xrange(2, n+1)并检查n <= 1时，循环将至少运行一次，因此curr将在循环之外定义。在

def fib_iter(n):
    if n <= 1:
        return n
    prev1, prev2 = 0, 1
    for i in xrange(2, n+1):
        curr = prev1 + prev2
        prev1, prev2 = prev2, curr
    return curr

（这是我的第一个家庭作业答案；社区可能会给我反馈，如果我宠坏了太多，我本可以做得更好）