如何在Scheme中自定义递归函数实现列表反转？

直观递归实现（基础版） #

最直观的递归思路是：反转一个列表，就是把第一个元素放到剩余列表反转结果的末尾。

(define (reverse lst)
  (if (null? lst)
      '()
      (append (reverse (cdr lst)) (list (car lst)))))

逻辑说明：

• 基线条件：当输入列表为空时，直接返回空列表'()（反转空列表还是空列表）
• 递归步骤：
  1. 先递归处理列表的剩余部分（(cdr lst)），得到反转后的子列表
  2. 用append把当前列表的第一个元素（(car lst)，需要用list转成单元素列表）拼接到子列表的末尾

注意：这个版本的时间复杂度是O(n²)，因为每次append操作都要遍历整个子列表，长列表场景下效率较低。

尾递归实现（高效版） #

用累加器优化的尾递归版本，避免重复遍历，时间复杂度为O(n)，且不会因递归深度过大导致栈溢出。

(define (reverse-tail lst)
  (define (reverse-helper lst acc)
    (if (null? lst)
        acc
        (reverse-helper (cdr lst) (cons (car lst) acc))))
  (reverse-helper lst '()))

逻辑说明：

• 内部辅助函数reverse-helper负责核心递归逻辑，参数acc是累加器，用来逐步构建反转后的列表
• 基线条件：当原列表为空时，累加器acc就是最终的反转结果
• 递归步骤：把当前列表的第一个元素(car lst)通过cons放到累加器的前面，然后递归处理剩余列表(cdr lst)
• 初始调用时，累加器设为空列表'()，作为反转的起点

测试示例 #

(reverse '(1 2 3 4))       ; 输出 (4 3 2 1)
(reverse-tail '(a b c d))  ; 输出 (d c b a)

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