频道栏目
读书频道 > web开发 > Javascript > JavaScript编程精解(原书第2版)
3.9 递归
2015-12-04 14:59:10     我来说两句
收藏   我要投稿
《高级程序设计(第3版)》是 超级畅销书的**新版。ECMAScript 5 和HTML5 在标准之争中双双胜出,使大量专有实现和客户端扩展正式进入规范,同时也为 增添了很多适应未来发展的新特性。本书这一版除增加5 章  立即去当当网订购

函数完全可以自己调用自己,只要避免栈溢出的问题即可。我们把函数调用自身的行为称为递归。我们可以利用递归来编写另一种风格的函数。比如说,power函数也可以按照以下方式编写:



 

 

这种代码风格更类似于数学当中的求幂运算,而且比通过循环乘法的方式更加优雅。该函数多次调用自身并传入不同参数,实现了多次乘法的操作。

但是这种实现方式有一个需要注意的问题:在标准的JavaScript实现当中,递归写法的函数执行效率比循环写法的函数慢了大约10倍。执行简单的循环操作比多次函数调用效率要高很多。

如何权衡性能与优雅是一个值得我们考虑的问题。就好比我们是希望代码更加人类友好还是更加机器友好呢?几乎所有程序都可以使用代码较多且复杂,但速度更快的方式实现,开发人员必须在这两者之间作出合适的权衡。

以之前的power函数为例,虽然使用循环的版本不够优雅,但也相当简单且易于理解,因此使用递归版本取而代之没有太多意义。但在更多情况下,若程序处理的概念非常复杂,为了确保程序简单易懂,牺牲一定效率也的确是一种明智的选择。

这里有一条基本原则:除非程序执行速度确实太慢,否则先不要关注效率问题。许多开发人员都遵循这条是原则,我也十分赞同这种做法。一旦出现速度太慢的情况,找出占用时间最多的部分,然后将其替换成效率更高的代码。

当然,该原则并不意味着开发人员可以完全忽视性能问题。许多情况下,像power这种函数,“优雅”的方式并没有多么简单。对于一位经验丰富的开发人员来说,有时候简单的方法并不意味着效率就更高。

我强调这一点的原因是许多编程初学者盲目地追求执行效率,哪怕只是一些非常小的细节,这一点让我感到十分诧异。这么做的结果就是代码冗长、复杂而且错误更多。相较于直截了当的编程方式,这种方法更加耗时,而且得到的性能提升十分有限。

但是,我们并不能以偏概全地说递归就只是比循环效率低。对于某些问题来说,递归相较于循环更能解决问题。这类问题通常需要执行和处理多个分支,而每个分支又会引出更多的执行分支。

我们考虑这样一个问题:从数字1开始,每次可以将数字加5或乘以3,循环执行。这样可以产生无穷多个新数字。那么如何编写函数来找出一个加法乘法序列,以产生指定的数字呢?例如,数字13可以通过1次乘法和2次加法生成,而数字15永远无法得到。

使用递归编码的解决方案如下所示:



 

 

需要注意的是该程序并不需要找出最短运算序列,只需要找出任何一个满足要求的序列即可。

这里并不需要读者对这段代码的工作原理有多么深入的了解。但我们可以通过它来培养我们通过递归解决问题的思路。

实际完成递归任务的是其内部的find函数。该函数接受两个参数,第一个参数是当前数字,第二个参数是一个字符串,记录了产生当前数字的运算过程。如果已经得到了目标数字则返回表示运算过程的字符串,否则返回null。

为了实现这个功能,该函数会从以下三个逻辑中选择一个执行。如果当前数字等于目标数字,即生成的加法乘法序列可以计算出目标数字,则直接返回当前的结果。如果当前数字大于目标数字,由于加法和乘法只能让数字变得更大,因此没有必要再继续执行了。最后,如果数字仍然小于目标数字,该函数会以当前数字为基础,尝试可能的两条计算路径,也就是进行两次递归调用,每次调用对应其中一条路径。如果第一次调用的返回值不是null,则直接返回。否则,无论生成的是字符串还是null,都进行第二次调用。

为了更好地理解函数执行过程,让我们来看一下find函数搜索数字13对应的加法乘法序列的调用情况:


 

这里的代码缩进表示调用栈的调用深度。第一次调用find时,函数分别使用(1 + 5)和(1 * 3)作为参数调用自身。首先计算(1 + 5),并尝试从计算结果6出发,递归找出小于等于目标数字的加法乘法序列。但这一过程找不到生成目标数字的计算过程,因此最后返回null。而||运算符使得我们可以计算(1 * 3),从3出发寻找新的计算过程。这一搜索过程十分顺利,因为第一次递归调用,通过另一次递归调用就得到了目标数字13,而无需再进行更多递归调用。最里面的递归调用返回一个字符串,每个间接调用则利用||运算符向调用者返回该字符串,最终将加法乘法序列返回给调用者。

您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力  
上一篇:3.8 闭包
下一篇:3.10 添加新函数
相关文章
图文推荐
排行
热门
最新书评
特别推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站