Racket集合并集函数实现异常，求递归优化及问题排查指导

你的代码存在的几个关键问题 #

• 递归终止条件错误：当其中一个列表为空时返回0，这会把无效值混入结果，且未处理剩余非空列表的元素
• 递归拼接逻辑混乱：你将递归调用的结果直接cons到当前列表前，导致每递归一层就多套一层括号，最终输出出现多层嵌套的怪异结构
• 未处理列表长度不一致的情况：如果两个列表长度不同，长列表剩余的元素会直接被忽略
• 缺少去重逻辑：集合的并集要求元素唯一，但你的代码只是简单合并元素，重复元素会被多次保留
• 滥用set!：Racket是函数式语言，应通过递归传递状态而非修改可变变量，这种写法极易导致逻辑混乱

修正后的实现方案 #

简单直观版（合并后去重） #

先合并两个列表，再去除重复元素，逻辑清晰易懂：

(define (union set1 set2)
  ;; 辅助函数：移除列表中的重复元素
  (define (remove-duplicates lst)
    (cond
      [(empty? lst) '()]
      [(member (first lst) (rest lst))
       (remove-duplicates (rest lst))]
      [else (cons (first lst) (remove-duplicates (rest lst)))]))
  ;; 合并两个列表后去重
  (remove-duplicates (append set1 set2)))

高效版（边合并边去重） #

如果想避免先合并再遍历的额外开销，可在合并过程中直接跳过重复元素：

(define (union set1 set2)
  (cond
    [(empty? set1) set2]
    [(member (first set1) set2)
     (union (rest set1) set2)]
    [else (cons (first set1) (union (rest set1) set2))]))

测试示例 #

(union '(1 2 3) '(2 3 4)) ; 输出 '(1 2 3 4)
(union '(1 1 2) '(2 3 3)) ; 输出 '(1 2 3)
(union '() '(1 2)) ; 输出 '(1 2)

原代码的具体问题拆解 #

你的build函数中，(set! lst (cons (build (rest build1) (rest build2) lst) lst))是嵌套结构的核心原因——每次递归的结果都会被当作一个元素塞进当前列表前面，最终形成((((...)) ...))的嵌套结构。另外(set! lst (cons lst a))的顺序完全颠倒，应该是把元素a加到列表头部，而非把列表加到元素前面，这也会导致元素顺序混乱。

内容的提问来源于stack exchange，提问作者RomanRhino