以图明志

计算机算法

[专题] 漫谈递归:尾递归与CPS

尾递归就是Continuation Passing Style
与普通递归相比,由于尾递归的调用处于方法的最后,因此方法之前所积累下的各种状态对于递归调用结果已经没有任何意义,因此完全可以把本次方法中留在堆栈中的数据完全清除,把空间让给最后的递归调用。这样的优化便使得递归不会在调用堆栈上产生堆积,意味着即时是“无限”递归也不会让堆栈溢出。这便是尾递归的优势。

计算机算法

[专题] 漫谈递归:补充一些Continuation的知识

Continuation在函数式编程是非常自然的
Continuation是一种非常古老的程序结构,简单说来就是entire default future of a computation, 即对程序“接下来要做的事情”所进行的一种建模,即为“完成某件事情”之后“还需要做的事情”。而这种做法,也可以体现在尾递归构造中。在函数式语言中,continuation的引入是非常自然的过程。

计算机算法

[专题] 漫谈递归:PHP里的尾递归及其优化

PHP编译器没有对尾递归进行优化
事实证明,尾递归在php中是没有任何优化效果的。一般的线性递归修改成为尾递归最大的优势在于减少了递归调用栈的开销。从php那个例子就明显看出来递归开销对程序的影响。但是并不是所有语言都支持尾递归的,即使支持尾递归的语言也一般是在编译阶段对尾递归进行优化,比如C语言对尾递归的优化。

计算机算法

[专题] 漫谈递归:从汇编看尾递归的优化

尾递归的编译器优化
对于尾递归,很多人的理解仅局限于它是递归和尾调用的一个合体,比普通递归效率高。至于效率为什么高,高在哪,可能没有深究过。 在执行函数B时,函数A的栈帧其实是已经大部分没用了,可以被修改或覆盖。编译器可以利用这一点进行优化,函数B执行后直接返回到函数A的调用者。
2 / 2 首页 < Prev 1 2 Next > 尾页 页码: