Scheme中非尾递归列表反转实现及TCO与列表顺序疑问

一、无需append的非尾递归列表反转方法？ #

纯函数式的非尾递归列表反转，没办法完全避开append（或其等价逻辑）。原因很直接：Scheme的cons只能在列表头部添加元素，而非尾递归反转需要先递归处理完子列表，再把当前元素放到子列表的末尾——而实现“放到末尾”的操作，本质上就是append的核心逻辑（遍历子列表直到尾部，再用cons追加元素）。

你之前写的复制列表的非尾递归代码，是因为把当前元素直接cons到子列表头部，自然只能得到原序列。如果要实现反转，必须把当前元素追加到子列表末尾，这就离不开append或者自己实现的等价逻辑，比如：

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

这段代码是非尾递归，确实实现了反转，但依赖append。如果完全不用append，纯函数式下非尾递归反转是做不到的——除非用可变结构的set-cdr!，但那已经脱离了纯函数式递归的范畴。

二、带累加器的TCO算法是否总是生成反转列表？非尾递归是否总是生成同序列表？ #

这两个结论都不成立，最终生成的序列完全取决于你编写的递归逻辑：

1. 带累加器的TCO算法可以生成原序列 #

比如用尾递归实现列表复制，我们可以先反向构建累加器，最后反转得到原序列：

(define (copy lst)
  (define (copy-tail lst acc)
    (if (null? lst)
        (reverse acc)  ; 最后反转累加器得到原序列
        (copy-tail (cdr lst) (cons (car lst) acc))))
  (copy-tail lst '()))

这里copy-tail是带累加器的尾递归（TCO友好），最终生成的是和原列表完全一致的序列，并非反转结果。

再比如，用尾递归给列表每个元素前加固定前缀，只要最后反转累加器，就能得到和原列表顺序一致的结果：

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

可见，带累加器的尾递归完全可以生成原序列，关键看你是否对累加器做最后反转，以及元素和累加器的组合方式。

2. 非尾递归算法可以生成反转列表 #

最典型的就是前面提到的用append的非尾递归反转函数，它是非尾递归，但生成的是反转后的列表。再比如，非尾递归实现的“把列表元素按从后到前的顺序平方”，生成的也是反转相关的序列：

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

这段非尾递归代码会返回原列表元素平方后的反转序列。

所以核心结论是：递归是否为尾递归、是否带累加器，和最终生成原序列还是反转序列没有必然联系——关键在于递归过程中如何组合当前元素和子问题的结果，以及是否对中间结果做反转处理。

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