阅读《The Little Schemer》：如何将Clojure版rember*函数改写为尾递归？

原版本的rember*并非尾递归实现——递归调用后仍需执行cons操作构建结果列表，递归返回值会参与后续计算，无法触发Clojure的栈优化，嵌套深度较大时可能引发栈溢出。

要改成尾递归，核心是用累加器保存已处理的结果，同时维护一个"工作栈"处理嵌套列表，确保每次递归调用都是函数的最后一步操作（用recur触发尾递归优化）。

尾递归实现代码 #

(defn rember*
  [a lat]
  (loop [worklist [lat]
         acc []]
    (if (empty? worklist)
      (reverse acc)
      (let [current (first worklist)
            rest-work (rest worklist)]
        (cond
          (empty? current)
            (recur rest-work acc)
          (clojure.inspector/atom? (first current))
            (let [elem (first current)]
              (if (= elem a)
                (recur (cons (rest current) rest-work) acc)
                (recur (cons (rest current) rest-work) (cons elem acc))))
          :else
            (recur (cons (first current) (cons (rest current) rest-work)) acc))))))

实现说明 #

• worklist：保存待处理的列表（包括嵌套子列表），确保深度优先的处理顺序和原函数一致。
• acc：累加器，用cons将符合条件的元素（或处理后的子列表结果）往前添加，最后通过reverse恢复正确顺序。
• 处理逻辑：
  1. 若worklist为空，返回反转后的累加器作为最终结果。
  2. 取出当前待处理的列表current：
     • 若current为空，直接处理worklist的剩余部分。
     • 若current首元素是原子：等于目标a则跳过，否则将元素加入累加器，继续处理current的剩余部分。
     • 若current首元素是子列表：将current的剩余部分压入worklist，优先处理子列表，保证嵌套结构的处理顺序和原函数一致。

测试示例 #

(rember* 'a ['a ['b 'a] 'c ['a 'd]])
;; => ['b 'c 'd]

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