ctf*_*ord 47 recursion functional-programming tail-recursion
尾递归是函数式语言中一个重要的性能优化策略,因为它允许递归调用消耗常量堆栈(而不是O(n)).
是否有任何问题根本无法以尾递归方式编写,或者总是可以将天真递归函数转换为尾递归函数？
如果是这样,有一天功能编译器和解释器可能足够智能以自动执行转换？
Jas*_*rff 47
是的,实际上你可以采取一些代码并转换每个函数调用 - 每次返回尾部调用.你最终得到的是持续传递风格,或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 Scheme会这样做,1994年在Chicken实施之前写的:CONS不应该反驳它的论点,第二部分:在MTA上的切尼
令人惊讶的是,延续传递风格在JavaScript中相当普遍.您可以使用它来执行长时间运行的计算,避免浏览器的"慢速脚本"弹出窗口.它对异步API很有吸引力.jQuery.get(一个简单的XMLHttpRequest包装器)显然是继续传递的风格; 最后一个参数是一个函数.
Nor*_*sey 26
观察到任何相互递归函数的集合都可以转换为尾递归函数,这是正确但没有用的.这个观察结果与20世纪60年代的旧栗子相当,可以消除控制流构造,因为每个程序都可以写成一个循环,其中嵌套了一个case语句.
有用的是,许多明显不是尾递归的函数可以通过添加累加参数转换为尾递归形式.(这种转换的一个极端版本是转换为延续传递方式(CPS),但大多数程序员发现CPS转换的输出很难阅读.)
这是一个"递归"函数的例子(实际上它只是迭代)但不是尾递归的:
factorial n = if n == 0 then 1 else n * factorial (n-1)
在这种情况下,乘法发生在递归调用之后.我们可以通过将产品放在累积参数中来创建尾递归的版本:
factorial n = f n 1
where f n product = if n == 0 then product else f (n-1) (n * product)
内部函数f是尾递归的,并编译成紧密循环.
我发现以下区别很有用:
在迭代或递归程序中,n通过首先解决一个大小的子问题来解决大小问题n-1.计算阶乘函数属于这一类,它可以迭代地或递归地完成.(这个想法概括为例如Fibonacci函数,你需要两者n-1并n-2解决它n.)
在递归程序中,n通过首先解决两个
大小的子问题来解决大小问题n/2.或者更一般地说,你解决一个大小的问题n
,首先解决大小的子问题k和大小的一个n-k,在那里1 < k <
n.Quicksort和mergesort是这类问题的两个例子,可以很容易地递归编程,但迭代编程或仅使用尾递归并不容易.(您基本上必须使用显式堆栈来模拟递归.)
在动态编程,你解决一个大小的问题n,首先解决所有
各种规模的子问题k,在这里k<n.在伦敦地铁上寻找从一个点到另一个点的最短路线就是这种问题的一个例子.(伦敦地铁是一个多重连接图,你可以通过首先找到最短路径为1档的所有点,然后最短路径为2档,等等来解决问题)
只有第一种程序才能简单地转换为尾递归形式.
Kri*_*son 11
任何递归算法都可以重写为迭代算法(可能需要堆栈或列表),并且迭代算法总是可以重写为尾递归算法,因此我认为任何递归解决方案都可以以某种方式转换为尾递归解决方案.
(在评论中,Pascal Cuoq指出任何算法都可以转换为延续传递方式.)
请注意,仅仅因为某些东西是尾递归并不意味着它的内存使用是不变的.它只是意味着调用返回堆栈不会增长.