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

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