functional-programming - 是否存在无法使用尾递归编写的问题？

Question

尾递归是函数式语言中重要的性能优化策略，因为它允许递归调用消耗常量堆栈(而不是 O(n))。

是否存在根本无法用尾递归风格编写的问题，或者是否总是可以将朴素递归函数转换为尾递归函数？

如果是这样，有一天函数式编译器和解释器可能会足够智能来自动执行转换吗？

Answer 1

是的，实际上您可以使用一些代码并将每个函数调用(以及每个返回)转换为尾调用。您最终得到的结果称为连续传递风格，或 CPS。

例如，这是一个包含两个递归调用的函数:

(define (count-tree t)
  (if (pair? t)
    (+ (count-tree (car t)) (count-tree (cdr t)))
    1))

如果将此函数转换为连续传递样式，结果如下:

(define (count-tree-cps t ctn)
  (if (pair? t)
    (count-tree-cps (car t)
                    (lambda (L) (count-tree-cps (cdr t)
                                                (lambda (R) (ctn (+ L R))))))
    (ctn 1)))

额外的参数ctn是一个count-tree-cps尾调用而不是返回的过程。 (sdcvvc 的答案说你不能在 O(1) 空间中完成所有事情，这是正确的；这里每个延续都是一个占用一些内存的闭包。)

我没有将对 car 或 cdr 或 + 的调用转换为尾部调用。这也可以完成，但我认为这些叶子调用实际上是内联的。

现在是有趣的部分。 Chicken Scheme实际上对其编译的所有代码都进行了这种转换。 Chicken 编译的程序永远不会返回。有一篇经典论文解释了 Chicken Scheme 这样做的原因，该论文写于 1994 年 Chicken 实现之前:CONS should not cons its arguments, Part II: Cheney on the M.T.A.

令人惊讶的是，连续传递风格在 JavaScript 中相当常见。可以使用to do long-running computation ，避免浏览器的“慢脚本”弹出窗口。它对于异步 API 很有吸引力。 jQuery.get (XMLHttpRequest 的简单包装)显然采用连续传递风格；最后一个参数是一个函数。