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

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 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和not n <= 1.因为n <= 1,fib(n)没有依赖关系,所以我们可以评估:

def fib_iter(n):
    if n <= 1:
        return n

现在我们需要涵盖另一个案例.我们先做一个依赖性分析.我们需要什么fib(n)用n > 1？我们打电话给fib(n-1)和fib(n-2).在迭代语言中,这些将是前两个值.显然,我们需要跟踪这些.我们将从那个问题的两个小案例开始:

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

(这是我的第一个作业答案; SO社区可能会给我反馈,如果我太过分了,我可以做得更好)