SICP 中的迭代阶乘过程

Question

这是生成递归过程的 SICP 的阶乘过程。

(define (factorial n)
  (if (= n 1) 
      1 
      (* n (factorial (- n 1)))))

现在这是相同的过程，但生成了一个迭代过程。在每个过程调用中，计数器递增到 n 并且乘积将自身乘以计数器。当不在块结构中时，fact-iter 有一个变量 max-count 实际上是 n.

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

我有点好奇为什么我们需要计数器，它除了自增并使用它的值来测试基本情况外并没有真正做任何事情。与递归过程一样，我们不能只做同样的过程，同时添加一个累加器使其迭代吗？例如：

(define (factorial n) 
(define (fact-iter product n)
  (if (= n 1)
      product
      (fact-iter (* n product)
                 (- n 1))))
  (fact-iter 1 n))

所以，这仍然是一个迭代过程，我认为这是一个比第一个例子更明显的过程。

不过，本书偏爱第一个例子肯定是有原因的。那么第一个迭代示例相对于第二个过程的优势是什么？

Answer 1

你的两个迭代版本是相同的，除了一个向上计数并与一个自由变量比较n，而另一个向下计数并与一个常量比较。

它不会对速度产生太大影响，所以我猜你认为你应该选择意图更明确的那个。有些人可能更喜欢上台阶。

有时您可能会明智地选择顺序。如果您要制作一个数字列表，您会选择与您想要的结果列表相反顺序的步骤，以便能够保持它的迭代：

(define (make-range to)
  (define (aux to acc)
    (if (> 0 to)
        acc
        (aux (- to 1) (cons to acc))))
  (aux to '()))

(define (make-reverse-range start)
  (define (aux n acc)
    (if (> n start)
        acc
        (aux (+ n 1) (cons n acc))))
  (aux 0 '()))

(make-range 10)          ; ==> (0 1 2 3 4 5 6 7 8 9 10)
(make-reverse-range 10)  ; ==> (10 9 8 7 6 5 4 3 2 1 0)

SICP 中的迭代阶乘过程

Iterative factorial procedure in SICP

lisp

recursion

scheme

sicp

factorial