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. 理解迭代的关键点是，每一时刻参数都保持有函数进一步运算的必要信息，而递归把这些信息放在了栈上，由系统隐式操作。

Quoted from SICP 1.2

In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process with the notion of a recursive procedure. When we describe a procedure as recursive, we are referring to the syntactic fact that the procedure definition refers (either directly or indirectly) to the procedure itself. But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a procedure is written. It may seem disturbing that we refer to a recursive procedure such as fact-iter as generating an iterative process. However, the process really is iterative: Its state is captured completely by its three state variables, and an interpreter need keep track of only three variables in order to execute the process.

One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose “looping constructs” such as do, repeat, until, for, and while. The implementation of Scheme we shall consider in chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar.

Apparently, RECURSIVE PROCESS is not identical to RECURSIVE PROCEDURE. I’m fooled by my previous knowledge gained from C and Java.