是否存在无法使用尾递归编写的问题？ [英] Are there problems that cannot be written using tail recursion?

问题描述

尾递归是功能语言中一个重要的性能优化策略，因为它允许递归调用消耗常量栈（而不是O（n））。

有没有问题不能用尾递归的方式编写，或者总是可以将一个天真递归函数转换为尾递归函数？

如果是这样，有一天，功能编译器和解释器可以足够聪明地自动执行转换吗？

解决方案

是的，实际上你可以取一些代码并将每个函数调用—以及每个返回—转换为尾部调用。例如，下面是一个包含两个递归调用的函数：
$

$ b pre code $（定义（count-tree t）
（if（pair？t）
（+（count-tree（car t））（ count-tree（cdr t）））
1））

看看你是否将这个函数转换为continuation-passing风格：

 （define（count-tree-cps t ctn）
（count-tree-cps（car t）
（lambda（L）（count-tree-cps（cdr t））
（lambda（R） （ctn（+ LR））））））
（ctn 1）））
  

额外的参数 ctn 是一个过程，它< count-tree-cps tail-calls 而不是返回。 （sdcvvc的回答说你不能在O（1）空间中做所有事情，这是正确的;这里每个延续都是一个闭包，它占用了一些内存。）

我没有将呼叫转换为 car 或 cdr 或 + 转换成尾部呼叫。这也可以做到，但我认为那些叶调用实际上会被内联。

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

令人惊讶的是，延续传递风格在JavaScript中相当普遍。您可以使用它进行长时间运行计算，避免浏览器的缓慢脚本弹出窗口。对于异步API来说这很有吸引力。 jQuery.get （一个简单的XMLHttpRequest封装）显然是一种持续传递的风格;最后一个参数是一个函数。

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?

解决方案

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

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

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.

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.

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屋！