Chinaunix首页 | 论坛 | 博客
  • 博客访问: 817962
  • 博文数量: 62
  • 博客积分: 526
  • 博客等级: 二等列兵
  • 技术积分: 2078
  • 用 户 组: 普通用户
  • 注册时间: 2012-02-04 20:41
个人简介

博客迁移至 freefe.cc

文章分类

全部博文(62)

分类: JavaScript

2014-09-01 22:23:50



    初略一看,的确递归实现阶乘很简单,不过很好的实现递归还是需要一点技巧的。

    递归即是程序在执行过程中不断调用自身的编程技巧,当然也必须要有一个明确的结束条件,不然就停不下来了好么~ 这边就简单的实现一下递归的阶乘。

  1. function factorial( n ){
  2.     return ( n <= 1 ) ? 1 : n * factorial( n-1 );
  3. }

    对于阶乘递归来说,由于其每次仅仅递归调用自身一次,所以不会引起一些较大的问题,但是对于一些相对一些相对复杂的递归,做一些技巧性的缓存还是很有必要的。比如递归最经典的使用场景就是计算斐波那契数列,但是每次调用过程中会在此调用自身函数两次,于是乎,2变4,4变8,量级成2指数级增长,当计算一些稍大的数时,便会遇到一些运行时间,或者有可能导致栈溢出。

  1. function fibonacci( n ){
  2.     return ( n <= 2 ) ? 1 : fibonacci( n-1 ) + fibonacci( n-2 );
  3. }

  4. function t(n){
  5.     console.time("a");
  6.     console.log( fibonacci( n ));
  7.     console.timeEnd("a");
  8. }


    上面便是具体数据,的确貌似有那么点的消耗大了点,毕竟才算到 42 就要 2s,毕竟测试的机子也算是中上级的,那么优化方式可以先使用缓存方式试试:

  1. var fibArr = [ undefined, 1, 1 ];
  2. function fibonacci( n ){
  3.     var nFib = fibArr[ n ];
  4.     return nFib
  5.          ? nFib
  6.          : ( fibArr[ n ] = fibonacci( n-1 ) + fibonacci( n-2 ) );
  7. }


    好吧,不多解释,这就是优化的结果。仔细想想可以感受到,我们将斐波那契数的计算量级从 2的指数 次级,降到了常量 n 次级,并且由于缓存,在多次运行将量级降得更低,然后运行速度简直把我和小伙伴都惊呆了。并且该方法也很好的缓解了栈溢出问题。

    要是没记错的话,有个理论是 所有的递归循环都可以转化成迭代循环

  1. function fibonacci( n ){
  2.     var x = 1, y = 1, i=2, t;
  3.     while( i < n ){
  4.         t = y;
  5.         y = x + y;
  6.         x = t;
  7.         i++;
  8.     }
  9.     return y;
  10. }



    貌似这下有点更牛逼了,其实他的量级与优化后带缓存的递归式一样的,不过他的量仅仅是计算,而递归的每个量都是调用一次方法,这也是两者最大的差别。

    好吧,自己的看法就简单的这么讲一下,关于递归方式,需要考虑仔细,一招棋下不好,就瘫了。不专业的属于方面请大家多多谅解,有错误欢迎指正,谢谢。

阅读(21235) | 评论(4) | 转发(4) |
给主人留下些什么吧!~~

lovenyf2016-02-22 10:48:03

柳飞花落:除了第一种方法,其他的计算出来的数值都是错误的,例如简单的求5的阶乘,5的阶乘是120,只有第一种方法是正确的,其它的得出的值都是5

后面的方法并不是阶乘 而是斐波那契数列的一个函数

回复 | 举报

柳飞花落2016-02-18 12:02:38

除了第一种方法,其他的计算出来的数值都是错误的,例如简单的求5的阶乘,5的阶乘是120,只有第一种方法是正确的,其它的得出的值都是5

lovenyf2015-03-12 10:39:15

cjz9032:factorial怎么变成fibonacci了!
这种标题党都行?

这使用场景而已

回复 | 举报

cjz90322015-03-11 10:26:29

factorial怎么变成fibonacci了!
这种标题党都行?