sicp-ex-3.17


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) >>