SICP ex 3.17 - 计数对 - 我不明白为什么我的答案出错了

Question

有人可以解释为什么下面的方法不起作用吗？我正在通过 SICP。本练习希望您编写一个函数来计算结构对的数量。程序用在三个结构上，都是三对。

(define (count-pairs x)
  (define (helper x encountered) 
    (if (or (not (pair? x)) (memq x encountered))  
        0
        (begin
          (set! encountered (cons x encountered))
          (+ (helper (car x) encountered)
             (helper (cdr x) encountered)
             1))))

  (helper x (list)))

正确的解法如下所示。可能出了什么问题？我注意到遇到的问题的处理方式略有不同，但我看不出哪里出了问题。

(define (count-pairs x)
  (let ((encountered '())) 
    (define (helper x) 
      (if (or (not (pair? x)) (memq x encountered)) 
          0 
          (begin 
            (set! encountered (cons x encountered)) 
            (+ (helper (car x)) 
               (helper (cdr x)) 
               1))))

    (helper x)))

输入（l1 和 y1）如下所示，但您不必尝试。

; 4 pairs counted with wrong way, 3 with correct way
(define l1 (list 1 2))
(define l2 (list 3))
(set-car! l1 l2)
(set-cdr! l2 (cdr l1))

; 7 pairs counted with the wrong way, 3 with correct way
(define y1 (list 1))
(define y2 (list 1))
(define y3 (list 1))
(set-car! y1 y2)
(set-cdr! y1 y2)
(set-car! y2 y3)
(set-cdr! y2 y3)

Answer 1

在您的回答中，您将 encountered 作为助手中的参数。这意味着每次使用 helper 都会有自己的 encounter 版本。当您阅读此表格时：

(+ (helper (car x) encountered)
   (helper (cdr x) encountered)
   1)

第二次递归将不会进行第一次递归的添加，因为您将添加到助手具有的绑定中，因此当代码恢复再次执行助手时，它会传递与传递给第一次递归的版本相同的版本。

通过 let 绑定，这样他的助手总是更新相同的自由变量，您可以避免存在多个版本的绑定。

SICP ex 3.17 - 计数对 - 我不明白为什么我的答案出错了

SICP ex 3.17 - Counting Pairs - I can't see why my answer goes wrong

scheme

sicp