这几天我看了几篇关于末尾递归的文章,以前对末尾递归没什么概念,所以就对末尾递归进行了回顾。
尾递归概念
末尾递归(Tail Recursion )的概念是递归概念的子集。 在通常的递归中,因为必须记住递归调用栈,所以由此产生的开销是不可估量的。 例如,以下php子句的第一个示例使用php编写阶乘函数是递归导致的堆栈溢出错误。 末尾递归出现的目的是消除递归堆栈损失这一缺点。
从代码层面来看,尾部递归其实可以用一句话说清楚:
函数的最后一个操作是递归调用
例如,“斐波那契”数列php的递归实现:
这是递归函数,但不是尾部递归。 因为fibonacci的最后一个操作是加法操作。
转换为尾部递归:
fibonacci2是末尾递归,追加2个累加器acc1和acc2,给出初始值。 记住,将递归转换为尾部递归的思想一定是增加累加器,减少递归外操作。
递归的应用因语言而异。 最常用的是函数式编程Erlang,其中几乎所有出现递归的函数都已修改为尾部递归。 谈尾部递归在几种不同语言中的表达及应用。
php中的末尾递归
我们做实验
正常递归:
末尾递归:
实验结果:
事实证明,
末尾递归在php中没有任何优化效果!
php的中尾递归没有如不安的飞鸟(http://Huo ding.com/2012/06/25/158 )的文章中所述进行优化,但是可以使用Trampoline的概念来消除递归。 这里也不说
c的末尾递归
C中的尾部递归优化是由gcc编译器完成的。 在gcc编译过程中添加-O2可以优化尾部递归
可以直接看到生成的汇编代码。
(gdb,gccO2 factorial.c使用ofactorial; disass factorial
在不添加-O2的情况下生成的程序集:
O2优化后的汇编:
请不要把头弄大。 我也是第一次看到汇编,这个代码非常简单,在网上稍微搜索一下指令,就可以大致理解了。
gcc确实在进行智能优化。
如果您感兴趣,可以使用-O3优化尾部递归,并查看其中的汇编指令
-O3的优化是直接展开循环
总结
一般的线性递归修正成为末尾递归的最大优点是减少了递归调用栈的开销。 通过php示例可以清楚地看到递归开销对程序的影响。 但是,并非所有语言都支持尾部递归。 即使在支持尾部递归的语言中,也通常在编译阶段优化尾部递归。 例如,上例中的C语言尾部递归优化。 在使用尾部递归优化代码时,必须首先了解此语言对尾部递归的支持。
我推荐几篇文章
php和lua尾部递归:
C尾递归分析:
golang尾递归讨论:
本文来源于檐脉刃博客园博客,原文链接: http://www.cn blogs.com/yjf 512/archive/2012/07/12/2588481.html,转载请联系原作者