recursion - 使用 Racket 递归返回列表

Question

我正在尝试从具有双重递归的方法返回一个列表(BST，二叉搜索树)。我正在尝试按如下方式实现它:

(define (mapBST BST someFunct)
  (cond
    [(null? BST)
     '()]
       [else (cons (car BST) (someFunct (car (cdr BST)))) (mapBST (car (cdr (cdr BST))) someFunct) (mapBST (car (cdr (cdr (cdr BST)))) someFunct) ]

  )
)

这是用这段代码调用的

(define bst 
             '( 3 "3"
                  ( 1 "1"
                     ()
                     ( 2 "2" () ())
                  )
                  ( 5 "5" () () )
            )
) 
(mapBST bst string->number)

我也试过这段代码，但它返回了 ((() ()) ()):

[else (printf (car (cdr BST))) (cons (mapBST (car (cdr (cdr BST))) someFunct) (mapBST (car (cdr (cdr (cdr BST)))) someFunct)) ]

结果应返回相同的 BST，但使用数字而不是字符串作为值。

Answer 1

在您的 else 表达式中，您没有正确地重建二叉搜索树，这就是您得到一个空列表的原因。将您的 else 案例更改为

...
[else
 (cons (car BST)
       (cons (someFunct (car (cdr BST)))
             (cons (mapBST (car (cdr (cdr BST))) someFunct)
                   (cons (mapBST (car (cdr (cdr (cdr BST)))) someFunct) empty))))]
...

或

...
[else
 (list (car BST)
       (someFunct (car (cdr BST)))
       (mapBST (car (cdr (cdr BST))) someFunct)
       (mapBST (car (cdr (cdr (cdr BST)))) someFunct))]
...

将解决您的问题(两个选项产生相同的列表，因为 (cons 1 (cons 2 empty)) 等同于 (list 1 2))。

这是 mapBST 的完整更新:

(define (mapBST proc BST)
  (cond
    [(null? BST) empty]
    [else
     (list (car BST)
           (proc (cadr BST))
           (mapBST proc (caddr BST))
           (mapBST proc (cadddr BST)))]))

例如，

(define BST '(3 "3" (1 "1" () (2 "2" () ())) (5 "5" () ())))
(mapBST string->number BST)
=> '(3 3 (1 1 () (2 2 () ())) (5 5 () ()))