我正在尝试从 SICP 进行练习 2.20。它引入了虚线尾符号。在我完成练习之前,我需要帮助来理解我编写的这个测试程序有什么问题:
(define (f . b)
(if (null? b) '() (cons (car b) (f . (cdr b)))))
当我在解释器中输入(f 1 2 3)
时,没有得到我期望的(1 2 3)
,我得到一个">超过最大递归深度"错误。
不过,我看不出我做错了什么。b
是列表(1 2 3)
,所以我应该得到(cons 1 (f . (2 3))
=>(cons 1 (cons 2 (f . (3))))
=>(cons 1 (cons 2 (cons 3 (f . ()))))
=>(1 2 3)
。
我怀疑问题是点符号仅适用于定义,但我想编写一个递归函数。我该怎么做?
虚线尾符号可以与define
一起使用,这意味着额外的参数被收集在一个列表中。在OP(define (f . b) ;...)
中,在像(f 1 2 3)
这样的函数调用中,b
被绑定到函数体中的列表(1 2 3)
。但是,不能在函数调用中使用虚线尾表示法。
但是,仅从尝试的函数调用(f . (cdr b))
中删除点也不起作用。问题是(cdr b)
是一个列表,所以在第一次递归调用之后,你有(f (cdr b))
这意味着传递给f
的值是列表(cdr b)
,并且由于函数的定义方式,这个列表被收集到另一个列表中并绑定到新函数体中的b
。
如果初始调用(f 1 2 3)
,则参数将被收集到一个列表中,以便b
在第一次调用中绑定到(1 2 3)
。然后(car b)
将被1
,后续调用将被(f (2 3))
。然后,参数(2 3)
将被收集到一个列表中,以便b
在第二次调用中绑定到((2 3))
。现在(car b)
是(2 3)
,这根本不是想要的。
本书后面将介绍apply
,这为摆脱这个难题提供了一条出路:
(define (g . b)
(if (null? b)
'()
(cons (car b) (apply g (cdr b)))))
但是,既然我们还不知道apply
,我们必须有创造力。另一种方法是在f
中定义一个帮助程序函数,该函数采用列表参数而不是任意数量的参数:
(define (f . b)
(define (helper xs)
(if (null? xs)
'()
(cons (car xs) (helper (cdr xs)))))
(helper b))
现在,递归调用是helper
,它需要一个列表参数。
示例交互:
> (g 1 2 3)
(1 2 3)
> (f 1 2 3)
(1 2 3)