使用虚线尾表示法的方案递归



我正在尝试从 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)

最新更新