如何在函数程序中实现尾递归

Question

例如

，以下 Scheme 中右折的朴素实现：

(define (fold-rite kons knil clist)
  (if (null? clist)
    knil
    (kons (car clist) (fold-rite kons knil (cdr clist)))))

这显然不是消除尾调用的候选者，因为fold-rite的递归调用必须在调用kons之前完成。现在，我可能有点聪明，改用延续传递样式：

(define (fold-rite-cps kons knil clist kontinuation)
  (if (null? clist)
    (kontinuation knil)
    (fold-rite-cps kons knil (cdr clist) 
      (lambda (x) (kontinuation (kons (car clist) x))))))

现在fold-rite-cps是尾递归的，但是在递归期间建立的中间延续仍然必须保留在某个地方。因此，虽然我可能不会吹出堆栈，但我仍然使用与第一个版本一样多的内存，不知何故，我感觉首先收集了一大堆延续，然后一举将它们全部解开应该对性能不利，尽管第二个版本实际上在我的机器上要快得多。

但是，如果左折叠可以在常量空间中运行

（减去正在累积的值），并且列表中的右折叠与其背面的左折叠相同，那么我想应该有一种方法来实现尾递归右折叠也可以在常量空间中运行。如果是这样，我将如何做？更一般地说，有什么方法可以将非尾递归函数变成尾递归函数，最好是可以在常量空间中运行的函数（假设显式循环可以用也在常量空间中运行的命令式语言编写）？我有没有做错的假设？

虽然我已经标记了Scheme和Lisp，但我对任何语言的解决方案都感兴趣;这些方法应该适用于一般的函数式程序。

Answer 1

根据上面的评论，我认为在不改变数据结构（缺点单元格）的情况下，最好的答案如下（在普通的 lisp 中，因为这是我手边的）。

由于缺点单元格的单一链接结构，为了不积累空间，我们将不得不几乎切换列表的顺序，然后折叠反向列表。 反转是一种线性空间运算，根据所使用的约简函数，归约可以是恒定空间。

(defun foldl (op clist &optional base)
  (if (null clist)
      base
      (foldl op (cdr clist)
             (funcall op (car clist) base))))
(defun foldr (op clist &optional base)
  ;; reverse the list then fold it
  (foldl op (foldl #'cons clist nil) base))

对于直接答案：不，不可能在恒定空间中折叠，因为 cons 单元格的单链接性质需要完整的列表遍历才能到达最后一个元素，然后是展开步骤或单独的列表来跟踪实际的折叠操作。