刚才在IBM DW上看到这篇《JavaScript 技巧与高级特性》，其中关于arguments.callee的部分有一个用递归来求斐波那契数列的例子，简化一下是这样的：

这种教科书式的写法出镜率很高，在很多文章里都可以看到，但是速度也特别慢，曾经看到过有些人就拿这种例子来说明“递归的效率低”或者“用javascript做函数式编程效率低”，然后给出迭代的写法……

更新：我今天老老实实的读了SICP的第一章之后发现书中对这个问题其实有很严谨的解释，为了防止自己被骂成民科，赶紧修正了一些说法，加了删除线的文字都是有错误的，新增加的文字用粗体。

其实这个方法速度慢并不是函数式编程（FP）的错，首先要把词义弄清楚，真正的数学意义上的“递归”（recursive）包含了“递推”（recurrence）和“回归”（regression）的过程，在程序执行的过程中，“递归”（recursive）指的是一种方法，把大的复杂的问题分解成更小更简单的问题，逐级分解下去，直到问题的规模小到可以直接求解，然后再逐级向上回溯直到解决最初的问题，用程序来实现这种算法的时候至少包含一次以上的递推执行过程，效率当然比不上直接作一次迭代。递归的计算过程（recursive process）包含了两个阶段，先逐级扩展（expansion），构造起一个由被推迟的操作组成的链条（会被解释器保存在堆栈里），然后在收缩（contraction）阶段逐级回溯执行那些操作。随着递归计算步骤的增多，这种方法消耗的资源会越来越大，而且会包含越来越多的冗余操作，上面那个求斐波那契数列的例子（在SICP里被称作“树形递归”）在这方面问题尤其严重，因为它的计算步骤会随着参数而指数性的增长。

引用SICP上的图解：

而在编程里常说的递归其实就是简单的指“自己调用自己”的过程，指的是一种语法形式，而不是计算过程，在SICP里使用“递归过程”（recursive procedure）这个词来称呼，表示“一个过程的定义中引用了该过程本身”，在FP里就是一个函数把状态作为参数反复调用自己，来实现迭代的效果，所以未必需要递推一次以上。，用递归过程也可以产生出迭代计算过程（iterative process，迭代计算过程中消耗的资源是一个常量），递归==迭代，这个表达式不仅在lisp,Erlang这类FP语言里成立，在javascript里也一样。

比如那个求斐波那契数列的例子就可以用尾递归：

跟这样的迭代方法是完全等价的：

速度测试：

都是从数列的起始处开始递推，区别只是：在迭代方法里是把每两个相邻的数相加的和保存在循环体外部的局部变量里，在尾递归方法中是把这个和作为参数传给下一次函数调用。

附带说一下，“尾递归”（Tail Recursion）指的是把计算过程集中在函数递归调用的最后一次把每次函数递归调用中的所有运算结果或操作都逐步传递到最末尾一次的函数调用，FP语言在编译/解释的时候都会把尾递归优化成一次直接的运算，而在javascript引擎里就算没有优化，至少也可以在每次调用过程中不留下任何痕迹，可以像普通的循环语句那样线性的推算到最后，因此无论速度还是内存消耗，都跟普通的迭代方法没有区别。

==============正文结束的分割线=================



吐槽时间到～

关于javascript的尾递归我估计肯定有很多人写过，Oliver Steele这样的大神就不用说了，中文的应该也有很多，我都懒得去google，所以如果火星了请一定要谅解………

我决定还是要尽量克服这种“火星恐惧症”，因为如果总是担心要写的东西太老土太平常太小白或是已经被人写过，大概就没办法在blog上交流技术了。我最近因为人际关系和情感上的问题比以前更自闭了，没心情写blog，没动力在javaeye发帖子，也没兴趣在IM上跟人说话……前几天跟一个在北京IBM做前端开发的同学说了几句话，好像是几个月来第一次跟陌生人交流……对了顺便说一下，在IM上找我的时候，请务必在第一句话里说明意图，即使在我被外向虚荣亢奋型人格占据的时间段里，对于只说一句“Hi”的聊天窗口，我也是会觉得不知所措并产生抗拒心理的……

最近准备参加两场技术交流活动，一个是29日的D2前端技术论坛，这次因为在魔都举办，所以我们土豆在名义和物质上是主办方，托CTO的关系在徐家汇微软的地盘借了一处场子（由于以前空空荡荡的土豆仓库早就被新员工挤满，还有一大堆门禁，不适合举办活动），但是听说报名人数已经超过500，场子装不下必须做筛选了……

之所以用“听说”这个词是因为我没参与任何组织工作，到时候也不用被推上台讲啥，自闭还是有好处的挖哈哈哈哈～～当初跟小麦同学讨论的时候，我建议请国外强者来撑场面，比如南征北战的javascript福音战士，Mozilla的John Resig，可惜没人推动……

另一个活动是12月4日在帝都举办的SD2.0大会，尽管在大萧条的背景下，我仍然义无反顾的在infoQ花1000rmb买了票……结果被证明投资失误……

如果吐槽的字数超过正文当然会是很囧的事情，所以虽然好久没在blog上写东西，我还是尽快收尾算了：

1，这个blog主要作为发布文章和项目的地方，所以如果我没有谷出自己喜欢的新鲜货，就不会有更新。我平时的更新多数都在twitter和friendfeed上。

2，我把twitter作为日常吐槽的地方，优点是可以约束我少写字，另外，我把twitter当作微博客而不是聊天/短信工具来使用：

http://twitter.com/dexteryy

3，我的分享主要发布在friendfeed，这是我目前最喜欢最常用依赖程度仅次于google reader的应用，欢迎订阅～

http://friendfeed.com/dexteryy

好了，趁着捣鼓斐波那契数列的热情，我要去看SICP和算法导论了……