如何用递归实现两个字符串列表的交集？（Dr.Racket）

当然可以用纯递归实现这个需求，你当前的代码问题在于：仅在第二个列表d2中移动指针遍历，没有对第一个列表d1的剩余元素进行完整检查——当d2遍历完但d1还有元素时，这些元素不会被再和d2的全部元素比对。

下面是仅用基础内置函数、纯递归的实现方案：

首先需要一个辅助递归函数，用来判断某个字符串是否存在于目标列表中：

(define (string-in-list? s lst)
  (cond
    [(empty? lst) #f]
    [(string=? s (first lst)) #t]
    [else (string-in-list? s (rest lst))]))

这个函数的逻辑：

• 如果列表为空，说明没找到目标字符串，返回#f
• 如果列表第一个元素等于目标字符串，返回#t
• 否则递归检查列表的剩余部分

然后是主函数both，遍历第一个列表的每个元素，判断是否在第二个列表中，收集符合条件的元素：

(define (both d1 d2)
  (cond
    [(empty? d1) empty]
    [(string-in-list? (first d1) d2)
     (cons (first d1) (both (rest d1) d2))]
    [else (both (rest d1) d2)]))

主函数的逻辑：

• 如果d1为空，返回空列表（基线条件）
• 如果d1的第一个元素存在于d2中，就把这个元素加入结果列表，然后递归处理d1的剩余部分和d2
• 如果不存在，直接递归处理d1的剩余部分和d2

比如测试用例：

(both '("a" "b" "c") '("b" "d" "a")) ; 返回 '("a" "b")

这个方案完全通过递归实现，只用到了empty?、first、rest、cons、string=?这些基础内置函数，符合你的要求。

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