浏览 3579 次
|
锁定老帖子 主题：函数式编程疑问
精华帖 (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中，这种实现将以大量栈和内存消耗为代价” 那到底尾递归该如何理解呢？ 我的测试正确的吗？ 声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：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保存. |
| 返回顶楼 | |
|
发表时间：2008-09-16
楼上各位怎么这样啊？看明白 LZ 想要讨论的问题是什么了吗？
怎么讥笑 LZ 不懂尾递归的有之，引经据典为 LZ 解释尾递归的也有之（LZ 也不容易啊，当了一年多的潜水员，才冒上来发个处女贴，马上就被拍得晕乎乎的，真是世态炎凉啊！呵呵！），稍仔细点看看就应该明白 LZ 想要讨论的是：“为什么我试验下来，尾递归的效率那么低？” 其实仔细想想，尾递归和迭代有多大区别？没多大吧！迭代也要使用堆栈，只不过那上面只放了当前操作数，中间结果放到了变量里，但当没有变量或变量不可变时，尾递归就是最好的选择，它把当前操作数与中间结果都放到了堆栈上（是比迭代多用了点堆栈，但相对的，它没使用变量。），因此，在相同的优化下，我想它们确实应该一样快。 我把 LZ 的代码放到了五个不同的浏览器中（IE7、FF3.01、Safari3.1.2、Opera9.50、Chrome0.2.149.29）执行，结果和楼主的差不多（Chrome 的结果很特别，下面说），这种情况我想是 JS 解释器的实现引起的，LZ 不应该选择 JS 来测试尾递归和迭代的效率。JS 虽然包含许多 FP 的特征，但同时它对命令式的支持也很好，它目标用户（脚本程序员）的头脑也大多是命令式的构成，他们不会也不想用递归来考虑问题，那么实现者当然要把用得最多的“for”好好优化一番，至于递归嘛，有就行了，反正也没人用，最多会用来写几个例子代码，展示一下 JS 的多范式编程能力。当然这只是我的猜测，我并不了解各个浏览器中 Javascript 解释器的具体实现，要完全搞明白也许只能跟踪一下，看看汇编码到底如何。 下面是各浏览器的测试结果： 我计算了 9 的阶乘，而且在尾递归函数中删除了“a = a||1”，直接用（9,1）来调用尾递归函数。所有的浏览器都是打开后拖入测试文档，第一次执行的结果，没有重复执行。 IE 迭代：1297 递归：5985 尾递归：7484 这些值没太大的意义，因为在 IE 的执行过程中，它已经弹出对话框说执行时间太长，问我是否要继续，这样的时间肯定不准了。 FF 迭代：381 递归：596 尾递归：554 Opera 迭代：484 递归：812 尾递归：844 Safari 迭代：312 递归：953 尾递归：985 Chrome 迭代：92 递归：89 尾递归：70 不比不知道，一比吓一跳，Chrome 实在太快了，但三个值非常接近，而且每次都不太一样，一下这个快点，一下那个快点，我不明白为什么会这样！我想加长它的执行时间，用 99 做为参数来调用，这时别的浏览器已经非常慢了，IE 更是等得没耐心，但 Chrome 还有 迭代：445 递归：713 尾递归：514 这样的表现，虽说这时递归版的函数已经溢出，但这个结果实在太让人吃惊了。 还有一个有意思的是，如果我们不让函数返回，也就是删掉每个函数的 return 关键字，这时的结果是：迭代与尾递归没什么变化，但递归版函数所用的时间将大大增加，在所有浏览器中都是这样。 |
| 返回顶楼 | |
|
发表时间：2008-09-16
上网了解了一番，看来 Javascript 的尾递归与迭代一样快的时代已经到来，看这里:
http://ejohn.org/blog/javascript-performance-rundown/ John Resig 介绍了三个浏览器(Javascript)测试套件: 1、SunSpider（只测试 Javascript 性能，objects, function calls, math, recursion 等，但不包含 rendering or DOM manipulation 。）； 2、V8 Benchmark（只测试 Javascript 性能，特别强调递归。）； 3、Dromaeo（大量的浏览器特性测试，包括 DOM 与 各种 JS 库。）。 Chrome 中的递归优化得很好，在 V8 Benchmark 测试中大比分领先，与我上面用 LZ 的代码测的情况相符，在 SunSpider 中 Chrome 也只比最新的 TraceMonkey 稍慢，但据说 TraceMonkey 有如此表现还是被递归拖了后腿，它的 recursion tracing 还没准备好，一旦完成，后果将……！哈哈！ LZ 可以去看看 V8 Benchmark 的测试代码。 |
| 返回顶楼 | |
|
发表时间：2008-09-17
我也认为现在的浏览器对尾递归的优化远远没做到位，未来一定会有改观。
|
| 返回顶楼 | |
