尾递归是函数式语言中重要的性能优化策略，因为它允许递归调用消耗常量堆栈（而不是 O(n)）。
是否存在根本无法用尾递归风格编写的问题，或者是否总是可以将朴素递归函数转换为尾递归函数？
如果是这样，有一天函数式编译器和解释器是否会足够智能来自动执行转换？
是的，其实你can获取一些代码并将每个函数调用（以及每个返回）转换为尾调用。你最终得到的就是所谓的延续传递风格，或 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 or cdr or +进入尾部调用。这也可以做到，但我认为这些叶子调用实际上是内联的。
现在是有趣的部分。鸡计划 http://www.call-with-current-continuation.org/实际上对它编译的所有代码都进行了这种转换。鸡编的程序永远不会回来。有一篇经典论文解释了 Chicken Scheme 这样做的原因，该论文写于 1994 年 Chicken 实施之前：反对者不应该反对其论点，第二部分：切尼关于 M.T.A. http://home.pipeline.com/~hbaker1/CheneyMTA.html
令人惊讶的是，连续传递风格在 JavaScript 中相当常见。你可以使用它进行长时间运行的计算 http://marijn.haverbeke.nl/cps/，避免浏览器的“慢脚本”弹出窗口。它对于异步 API 很有吸引力。jQuery.get http://www.webmonkey.com/tutorial/Easy_XML_Consumption_using_jQuery?oldid=20032（XMLHttpRequest 的简单包装）显然采用连续传递风格；最后一个参数是一个函数。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
