方案：递归过程比迭代快得多

Question

我正在研究 SICP 并编写了两个程序来计算 1/n^2 的和，第一个生成递归过程，第二个生成迭代过程:

(define (sum-rec a b)
  (if (> a b)
      0
      (exact->inexact (+ (/ 1 (* a a)) (sum-rec (1+ a) b)))))

(define (sum-it a b)
  (define (sum_iter a tot)
    (if (> a b)
        tot
        (sum_iter (1+ a) (+ (/ 1 (* a a)) tot))))
  (exact->inexact (sum_iter a 0)))

我测试了当使用 b 的小值调用时，这两个程序给出了完全相同的结果，并且随着 b 变大，结果接近 $pi^2/6$，因为预期。

但令人惊讶的是，调用 (sum-rec 1 250000) 几乎是瞬时的，而调用 (sum-it 1 250000) 则需要很长时间。

有什么解释吗？

Answer 1

正如评论中提到的，sum-it 目前的形式是使用精确算法对数字进行加法，这比 sum-rec 中使用的不精确算法要慢。要进行等效比较，您应该这样实现它：

(define (sum-it a b)
  (define (sum_iter a tot)
    (if (> a b)
        tot
        (sum_iter (1+ a) (+ (/ 1.0 (* a a)) tot))))
  (sum_iter a 0))

请注意，将 1 替换为 1.0 会强制解释器使用不精确的算术。现在这将 return 立即：

(sum-it 1 250000)
=> 1.6449300668562465

Answer 2

您可以重构这两个版本，以便它们可以适当地进行精确或不精确的算术运算，只需控制它们用于零的值并依赖于传染规则即可。这两个在 Racket 中，默认情况下没有 1+ 但对于带有默认值的可选参数确实有一个很好的语法：

(define (sum-rec low high (zero 0.0))
  (let recurse ([i low])
    (if (> i high)
      zero
      (+ (/ 1 (* i i)) (recurse (+ i 1))))))

(define (sum-iter low high (zero 0.0))
  (let iterate ([i low] [accum zero])
    (if (> i high)
        accum
        (iterate (+ i 1) (+ (/ 1 (* i i)) accum)))))

这样做的好处是您可以很容易地看到两个版本的性能差异。缺点是你需要一个非常聪明的编译器来优化这里的数值运算（我认为，即使它知道 low 和 high 是机器整数，它也必须推断出zero 将是某种数值类型，并为所有可能的类型生成函数体的副本。

方案：递归过程比迭代快得多

Scheme : recursive process much faster than iterative

lisp

scheme

sicp