The text suggests that one should use a structure to keep track of pairs that have already been encountered. Notice that there is a let statement defining encountered around the internal definition of a helper function, so that this list is recreated every time count-pairs is invoked, and so that the helper has access to all encountered pairs at any point of execution. Also, notice that this implementation of count-pairs does not address the problem of cycling. (why? works nicely with a self-referencing list; Erik)
(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)))
<< Previous exercise (3.16) | Index | Next exercise (3.18) >>