如何用带累加器的尾递归实现Racket有序列表合并？

需求说明 #

合并两个有序列表(40 43 50)和(42 46 48)，得到有序结果(40 42 43 46 48 50)，要求通过带累加器的尾递归函数实现。

原代码问题分析 #

你提供的代码存在几个关键问题：

• 辅助函数rec仅为空定义，缺少核心逻辑
• 调用rec时参数传递语法错误，未正确传递剩余列表和更新后的累加器
• 未处理累加器的逆序问题，最终结果会顺序颠倒
• 存在未闭合的括号，语法不完整

正确实现代码 #

;; 尾递归辅助函数，带累加器
(define (merge-tail-rec l1 l2 acc)
  (cond
    ;; 若l1为空，反转累加器后拼接剩余的l2（l2本身有序）
    ((null? l1) (append (reverse acc) l2))
    ;; 若l2为空，反转累加器后拼接剩余的l1（l1本身有序）
    ((null? l2) (append (reverse acc) l1))
    ;; 比较两个列表首元素，将较小的加入累加器，递归处理剩余列表
    ((<= (car l1) (car l2))
     (merge-tail-rec (cdr l1) l2 (cons (car l1) acc)))
    (else
     (merge-tail-rec l1 (cdr l2) (cons (car l2) acc)))))

;; 主函数，调用辅助函数并传入初始空累加器
(define (merge l1 l2)
  (merge-tail-rec l1 l2 '()))

逻辑解释 #

1. 尾递归特性：辅助函数merge-tail-rec的最后一步是调用自身，没有后续计算，符合尾递归要求，不会产生栈溢出问题
2. 累加器作用：累加器acc暂存已经筛选出的元素，由于cons是往列表头部添加元素，所以acc中的元素是逆序的，最后通过reverse转为正序
3. 终止条件：当其中一个列表为空时，将反转后的累加器与剩余的有序列表拼接（剩余列表本身已经有序，直接追加即可）
4. 递归逻辑：每次递归时比较两个列表的首元素，将较小的元素加入累加器，然后递归处理对应的剩余列表

测试示例 #

调用(merge '(40 43 50) '(42 46 48))，将返回结果(40 42 43 46 48 50)，符合预期。

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