Exercise 3.16 · 习题

Exercise 3.16: Ben Bitdiddle decides to write a
procedure to count the number of pairs in any list structure. “It’s easy,”
he reasons. “The number of pairs in any structure is the number in the
car plus the number in the cdr plus one more to count the current
pair.” So Ben writes the following procedure:

(define (count-pairs x)
(if (not (pair? x))
0
(+ (count-pairs (car x))
(count-pairs (cdr x))
1)))

Show that this procedure is not correct. In particular, draw box-and-pointer

diagrams representing list structures made up of exactly three pairs for which

Ben’s procedure would return 3; return 4; return 7; never return at all.

练习 3.16：Ben Bitdiddle 决定编写一个过程，用于统计任意表结构中序对的数量。他认为：“这很简单。任何结构中序对的数量，等于 car 部分的序对数加上 cdr 部分的序对数，再加上 1 以计入当前这个序对。”于是 Ben 写出了如下过程：

(define (count-pairs x)
(if (not (pair? x))
0
(+ (count-pairs (car x))
(count-pairs (cdr x))
1)))

请证明这个过程是不正确的。具体而言，请画出恰好由三个序对组成的表结构的箱形图，使得 Ben 的过程分别返回 3；返回 4；返回 7；以及永远不返回。