有没有用尾递归写不出来的问题? [英] Are there problems that cannot be written using tail recursion?

问题描述

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

Tail recursion is an important performance optimisation stragegy in functional languages because it allows recursive calls to consume constant stack (rather than O(n)).

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

Are there any problems that simply cannot be written in a tail-recursive style, or is it always possible to convert a naively-recursive function into a tail-recursive one?

如果是这样，有朝一日函数式编译器和解释器可能足够智能以自动执行转换吗?

If so, one day might functional compilers and interpreters be intelligent enough to perform the conversion automatically?

推荐答案

是的，实际上您可以使用一些代码并将每个函数调用—和每个 return—转换为尾调用.你最终得到的是所谓的持续传递风格，或 CPS.

Yes, actually you can take some code and convert every function call—and every return—into a tail call. What you end up with is called continuation-passing style, or CPS.

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

For example, here's a function containing two recursive calls:

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

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

And here's how it would look if you converted this function to continuation-passing style:

(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) 空间中做所有事情，这是正确的；这里每个延续都是一个占用一些内存的闭包.)

The extra argument, ctn, is a procedure which count-tree-cps tail-calls instead of returning. (sdcvvc's answer says that you can't do everything in O(1) space, and that is correct; here each continuation is a closure which takes up some memory.)

我没有将 car 或 cdr 或 + 的调用转换为尾调用.也可以这样做，但我认为这些叶调用实际上是内联的.

I didn't transform the calls to car or cdr or + into tail-calls. That could be done as well, but I assume those leaf calls would actually be inlined.

现在是有趣的部分.Chicken Scheme 实际上对它编译的所有代码进行了这种转换.由Chicken编译的程序永不返回.有一篇经典论文解释了为什么 Chicken Scheme 会这样做，它写于 1994 年，在 Chicken 实施之前:CONS 不应该反对其论点，第二部分:切尼关于 MTA

Now for the fun part. Chicken Scheme actually does this conversion on all code it compiles. Procedures compiled by Chicken never return. There's a classic paper explaining why Chicken Scheme does this, written in 1994 before Chicken was implemented: CONS should not cons its arguments, Part II: Cheney on the M.T.A.

令人惊讶的是，continuation-passing 风格在 JavaScript 中相当普遍.您可以使用它进行长时间运行的计算，避免浏览器的慢速脚本"弹出窗口.它对异步 API 很有吸引力.jQuery.get(XMLHttpRequest 的简单包装器)显然是连续传球风格；最后一个参数是一个函数.

Surprisingly enough, continuation-passing style is fairly common in JavaScript. You can use it to do long-running computation, avoiding the browser's "slow script" popup. And it's attractive for asynchronous APIs. jQuery.get (a simple wrapper around XMLHttpRequest) is clearly in continuation-passing style; the last argument is a function.

这篇关于有没有用尾递归写不出来的问题?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！