如何创建尾递归反向列表程序？

Question

这个问题与 How to Reverse a List? 类似，但针对的是迭代（尾递归）函数。我怎样才能创建这样的功能？可能吗？

Answer 1

是；事实上 reverse 的标准实现完全是尾递归的。

(define (reverse xs)
  (fold cons '() xs))

不喜欢使用 fold？没问题：

(define (reverse xs)
  (do ((result '() (cons (car xs) result))
       (xs xs (cdr xs)))
      ((null? xs) result)))

Answer 2

或更明确：

    (define (reverse xs)
     (let loop ((pend xs)
                (res '()))
       (if (null? pend)
           res
           (loop (cdr pend) (cons (car pend) res)))))

Chris 的 fold 回答更简洁并且性能更好（出于各种原因）。至于你的问题的第二部分，它总是可能的，即每个函数都可以成为尾递归的（例如，通过转换为 cps，这可以机械地完成）。

如何创建尾递归反向列表程序？

How to create tail recursive reverse list procedure?

function

recursion

scheme

reverse

tail-recursion