不知道如何解决 SICP 练习 1.11

练习1.11 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_thm_1.11:

一个功能f由以下规则定义f(n) = n if n < 3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n > 3。编写一个计算过程f通过递归过程。编写一个计算过程f通过迭代过程。

递归地实现它非常简单。但我不知道如何迭代地做到这一点。我尝试与给出的斐波那契示例进行比较，但我不知道如何使用它作为类比。所以我放弃了（为我感到羞耻）并谷歌搜索一个解释 http://www.billthelizard.blogspot.com/2009/11/sicp-exercise-111.html，我发现了这个：

(define (f n)
   (if (< n 3)
       n
       (f-iter 2 1 0 n)))

(define (f-iter a b c count)
   (if (< count 3)
       a
       (f-iter (+ a (* 2 b) (* 3 c))
               a
               b
               (- count 1))))

读完后，我了解了代码及其工作原理。但我不明白的是从函数的递归定义到此所需的过程。我不明白代码是如何在某人的头脑中形成的。

您能解释一下达成解决方案所需的思维过程吗？

您需要捕获某些累加器中的状态并在每次迭代时更新状态。

如果您有使用命令式语言的经验，请想象编写一个 while 循环并在循环的每次迭代期间跟踪变量中的信息。你需要什么变量？您将如何更新它们？这正是您在Scheme 中进行迭代（尾递归）调用集所必须要做的。

换句话说，开始将其视为 while 循环而不是递归定义可能会有所帮助。最终，您将足够流畅地进行递归 -> 迭代转换，无需额外的帮助即可开始。

对于这个特定的示例，您必须仔细查看三个函数调用，因为并不能立即清楚如何表示它们。然而，这是可能的思考过程：（在Python伪代码中强调命令性）

每个递归步骤都会跟踪三件事：

f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) 

所以我需要三个状态来跟踪当前、最后一个和倒数第二个值f。 （那是，f(n-1), f(n-2) and f(n-3)。） 给他们打电话a, b, c。我必须在每个循环内更新这些部分：

for _ in 2..n:
    a = NEWVALUE
    b = a
    c = b
return a

那么什么是NEWVALUE？好吧，现在我们已经有了代表f(n-1), f(n-2) and f(n-3)，这只是递归方程：

for _ in 2..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

现在剩下的就是找出初始值a, b and c。但这很容易，因为我们知道f(n) = n if n < 3.

if n < 3: return n
a = 2 # f(n-1) where n = 3
b = 1 # f(n-2)
c = 0 # f(n-3)
# now start off counting at 3
for _ in 3..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

这与Scheme迭代版本还是有点不同，但我希望你现在能看到这个思考过程。