Liuw's Thinkpad

中文实在不清楚Process和Procedure如何进行区别，所以题目写了英文。

SICP习题1.11

A function f is defined by the rule that f(n) = n if n = 3 and f(n) = f(n-1) + 2f(n-2) + 3f(n-3) if n >= 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an interative process

SICP中已经给了一个例子，把linear recursive转化为iterative。后面一个要求其实是要把tree recursive进行转化。

好吧，递归的很简单。

(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))

我比较笨点，迭代的想了好久，写出来个挺锉的。

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

(define (f-aux product a b c count n)
  (if (> count n)
      product
      (f-aux (+ a (* 2 b) (* 3 c))
             (+ a (* 2 b) (* 3 c))
             a
             b
             (+ count 1)
             n)))

这个代码是有冗余的。并不需要专门用一个product去记录结果。写出这样的代码，其实是对“迭代”理解得还不够深刻。改进后的代码是这样的。

(define (f n)
  (if (< n 3)
      n
      (f-aux  4 2 1 2 n)))

(define (f-aux a b c count n)
  (if (> count n)
      c
      (f-aux (+ a (* 2 b) (* 3 c))
             a
             b
             (+ count 1)
             n)))

count并不是必要的，可以直接用n自减到0即可。

ChinaUnix的win_hate也给出了一个版本。我改写了一下，好看点。

(define (g n)
  (g-aux 0 1 2 n))

(define (g-aux x y z n)
  (if (= 0 n)
      x
      (g-aux y z (+ (* 3 x) (* 2 y) z) (- n 1))))

但是这个版本的定义域默认是非负整数，我觉得这是不合适的，因为题目中没有明确指出这一点。

总结一下，有几点比较有意思的：

1. 线性递归和树形递归的尾递归情况，可以转化为迭代，其他情况未考究；
2. 转化时，关键是总结出各个参数的关系，没有必要使用专门的参数去记录结果；
3. 理解迭代的关键点是，每一时刻参数都保持有函数进一步运算的必要信息，而递归把这些信息放在了栈上，由系统隐式操作。

© 2010, liuw. All rights reserved.