SICP 习题 (1.11) 解题总结

SICP 习题 1.11相对简单一点，主要是里面没有太多数学问题，数学还是有一点，让这些数学天才们不使用数学样例它们可能宁愿不写书了。

题目要求我们定义一个过程实现函数f，f的规则是：

如果n< 3那么f（n) =n

如果n>=3那么f(n)= f(n-1) + 2f (n-2) + 3f(n-3)

要求用递归实现一遍，然后用迭代实现一遍

这个题目差不多是书中1.2.2节提到的“斐波那契数”的翻版，就是斐波那契数是前两个数相加，而这个是前三个数相加，同时加了一些“乘2”，“乘3”的操作。

书中讲到斐波那契数主要是为了讲解树形递归，所谓树形递归可以简单地理解为一个过程两次以上递归调用自己，作为程序员的我们应该不难理解这个概念。

因为斐波那契数经常被当作递归教材的例子，所以很多人应该都熟悉这个数学概念，这里就不详细讲了，不明白的人仔细看一下书中的内容也应该可以理解。

归于题目的递归解，做起来还是比较简单的，递归解的好处就是比较直观，我做的答案如下：

(define (myf n)
  (format #t "Caculating n, n is ~S ~%" n)
  (if (< n 3) n 
      (+ (myf (- n 1)) (* 2 (myf (- n 2))) (* 3 (myf (- n 3))))))

做迭代解的话稍微麻烦一点点，就是要想明白从哪里开始计算，如何替换中间数，如何结束。

对于这里的函数f(n)，需要将前三个数的计算结果加起来，我们就从0 1 2 三个数开始，将（0*3）（1*2） 2三个数加起来作为第四个数，然后将1 2 和"（0*3）+（1*2）+ 2"作为需要处理的三个数重新代入函数f中，这样就通过迭代实现了本来用递归实现的函数，函数代码如下：

(define (myf-iter a b c n)
  (format #t "Caculating n, n is ~S, a is ~S, b is ~S, c is ~S ~%" n a b c)
  (if (= n 0)
      a
  (myf-iter b c ( + (* 3 a) (* 2 b) c) (- n 1))))

(define (newf n)
  (myf-iter 0 1 2 n))

因为习题1.11比较简单，就不罗嗦了。