方案 : recursive process much faster than iterative

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 值调用时，这两个过程给出了完全相同的结果，并且结果接近 $pi^2/6$ 作为 b正如预期的那样变大。

但令人惊讶的是，调用 (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 会强制解释器使用不精确的算术。现在这将立即返回:

(sum-it 1 250000)
=> 1.6449300668562465