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

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 是尾递归的，但在递归过程中建立的中间 continuation 仍然需要被存储在某个地方。因此，虽然我可能不会爆栈，但我仍然使用了与第一个版本相同的内存量。而且我总觉得，先收集大量的 continuations，然后一下子展开它们应该对性能不利，尽管第二个版本在我的计算机上实际上要快得多。

但是，如果左折叠可以在常量空间（减去正在累加的值）中运行，而列表上的右折叠与其反转后的左折叠相同，那么我想应该有一种方法来实现一个尾递归的右折叠，它也可以在常量空间中运行。如果有的话，我该怎么做呢？更具体地说，有哪些方法可以将非尾递归函数转换为尾递归函数，最好是可以在常量空间中运行（假设在命令式语言中可以编写显式循环，该循环也可以在常量空间中运行）？我是否有任何错误的假设？

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

- jaymmer - Reinstate Monica

---

如果左折叠可以在常量空间中运行（减去正在累加的值），并且列表上的右折叠与其反转上的左折叠相同，那么我想应该有一种实现尾递归右折叠也可以在常量空间中运行的方法。如果最终结果是“在反转列表上执行左折叠”或其变体，您会感到失望吗？ - Joshua Taylor

我有点想知道是否可以省略那一步。尽管我突然意识到，可能不行，因为你不能在不遍历列表的情况下进行右折叠，总会在某个时候以某种方式遍历列表，所以...我应该再考虑一下这个问题。 - jaymmer - Reinstate Monica

可以将尾调用折叠到左侧或右侧，但必须实现自己的双向链表和相应的迭代器函数。或者只需使用向量/数组。通常，如果您可以在不必累加的情况下迭代（在迭代器函数本身中，而不是在累加器函数中），并且使用恒定空间累加器进行累加（例如计数、最大值、最小值、总和、指向最后一个 cons 的指针），则具有良好的尾调用候选项。如果不能（例如迭代反向单链表或累加中位数），仍应考虑不使用调用堆栈。 - acelent

有时候你可以使用尾递归模除法 https://en.wikipedia.org/wiki/Tail_call#Tail_recursion_modulo_cons。有时kons可以转换为关联的“append”，因此可以编写一个累积版本。当一切都失败时，有CPS，而续体可以被实现为某些数据结构，而不是实际的lambda，并且在收集所有数据（整个列表被扫描）后进行处理（我模糊地记得Reynolds' https://en.wikipedia.org/wiki/Defunctionalization与此有关）。有时在构建时可以简化这些堆上的数据。 - Will Ness

请参见 https://stackoverflow.com/search?tab=newest&q=defunctionalization，特别是 https://dev59.com/p2ox5IYBdhLWcg3wQSKp。 - Will Ness

Answer 1

基于以上评论，我认为在不改变数据结构（cons单元）的情况下，最好的答案如下（使用Common Lisp，因为我手头有这个）。

由于cons单元具有单链结构，为了不积累空间，我们必须基本上交换列表的顺序，然后折叠反转的列表。反转是线性空间操作，而减少可能是常数空间，这取决于所使用的减少函数。

(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))

直接回答：不，无法在常量空间中进行foldr操作，因为cons单元的单链特性需要对整个列表进行遍历才能到达最后一个元素，然后需要进行解绑步骤或使用单独的列表来跟踪实际的折叠操作。

- bobbysmith007