在 Python 中:
def g(n):
if n <=3:
return n
return g(n-1) + 2 * g(n-2) + 3 * g(n-3)
我明白这个函数在做什么，但我似乎不知道如何让它迭代。请帮助。如果可能，请提供解释，以便我能完全理解问题。
请您参考如下方法:
这看起来类似于斐波那契数列问题，并且以迭代方式实现起来并不简单。它看起来也像是家庭作业，所以我将发布获取斐波那契迭代的步骤，您应该能够将其应用于您的问题。
如果你不知道，斐波那契是这样定义的:
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
我希望这是相当明显的。然后我们按照在递归方法中解析的顺序解析函数。当展开递归并分析函数时，我们发现第一个要计算的非平凡值当然是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 社区可能会给我反馈，如果我剧透太多，我本可以做得更好)
