浏览 298 次
|
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
时间：2008-08-04
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<script language="JavaScript" type="text/JavaScript">
function oldRecursion(n){
var j=1;
for(var i=n;i>0;i--){
j*=i;
}
return j;
}
function recursion(n){
return n==1?1:n*recursion(n-1);
}
function tailRecursion(n, a){
a = a||1;
return n==1?a:tailRecursion(n-1, a*n);
}
// -----------------------------------------------------------------------------------------
var start=new Date();
for(var i=0;i<100000;i++){
r1=oldRecursion(3);
}
var end=new Date();
document.write(""+(end-start)+"<br/>");
// -----------------------------------------------------------------------------------------
var start=new Date();
for(var i=0;i<100000;i++){
r2=recursion(3);
}
var end=new Date();
document.write(""+(end-start)+"<br/>");
// -----------------------------------------------------------------------------------------
var start=new Date();
for(var i=0;i<100000;i++){
r3=tailRecursion(3);
}
var end=new Date();
document.write(""+(end-start)+"<br/>");
document.write(r1+" "+r2+" "+r3);
// -----------------------------------------------------------------------------------------
</script>
</html>
我在jstang看到过一个帖子“阶乘(factorial)&尾递归(Tail Recursion)http://jstang.5d6d.com/thread-1750-1-1.html” 里面讲“效率上和循环迭代、阶乘改进算法相当甚至稍胜出（ie6,firefox2,safari3），普通递归的效率最为底下，且需要深入堆栈” 但是测试表明 尾递归效率最低啊 结果是：
js语言精髓与编程实践里面也说啦“然而不幸的是。目前已知的javascript 的解释环境中并不支持这种特性（尾递归）。因此，我们在这里讨论函数室式时，可以说“能够通过函数递归来消灭循环语句”，但在不支持尾递归（及其优化技术）的javascript中，这种实现将以大量栈和内存消耗为代价” 那到底尾递归该如何理解呢？ 我的测试正确的吗？ 声明：JavaEye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
|
| 返回顶楼 | |
|
时间：2008-08-07
换一个支持尾递归的测试
|
| 返回顶楼 | |
|
时间：2008-08-07
我已经不是第一次看到自称程序员连尾递归都不知道的人了
真的，很好奇 这些人们上大学的时候都干嘛呢？ 怎么学会编程的？必定有些什么我等资质愚钝者所不解的秘诀吧？ |
| 返回顶楼 | |
|
时间：2008-08-07
引用 尾递归是针对传统的递归算法而言的, 传统的递归算法在很多时候被视为洪水猛兽. 它的名声狼籍, 好像永远和低效联系在一起.
尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去. 以下是具体实例: 线性递归: long Rescuvie(long n) {
return(n == 1) ? 1 : n * Rescuvie(n - 1);
}
尾递归: long TailRescuvie(long n, long a) {
return(n == 1) ? a : TailRescuvie(n - 1, a * n);
}
long TailRescuvie(long n) {//封装用的
return(n == 0) ? 1 : TailRescuvie(n, 1);
}
当n = 5时 对于线性递归, 他的递归过程如下: Rescuvie(5)
{5 * Rescuvie(4)}
{5 * {4 * Rescuvie(3)}}
{5 * {4 * {3 * Rescuvie(2)}}}
{5 * {4 * {3 * {2 * Rescuvie(1)}}}}
{5 * {4 * {3 * {2 * 1}}}}
{5 * {4 * {3 * 2}}}
{5 * {4 * 6}}
{5 * 24}
120
对于尾递归, 他的递归过程如下: TailRescuvie(5) TailRescuvie(5, 1) TailRescuvie(4, 5) TailRescuvie(3, 20) TailRescuvie(2, 60) TailRescuvie(1, 120) 120 很容易看出, 普通的线性递归比尾递归更加消耗资源, 在实现上说, 每次重复的过程 调用都使得调用链条不断加长. 系统不得不使用栈进行数据保存和恢复.而尾递归就 不存在这样的问题, 因为他的状态完全由n和a保存. |
| 返回顶楼 | |
