云课堂作业---斐波那契数列的引发的思索

UCloud 发布于2019-08-21 17:42 / 2826人阅读

摘要：闭包尾递归循环迭代实现使用方式，主要是看实现思想从图中我们可以很明显的看出，使用尾递归计算斐波那契数列性能完胜直接递归和闭包，特别是当数值比较大的时候，尾递归的作用就越明显。

前端微专业JavaScript有一道题目是求斐波那契数列的，一开始没想很多，觉得实现功能自己已经很棒棒了（逃）
后面有同学讨论直接递归特别耗费时间，开始考虑使用闭包，看我们讨论的不亦乐乎的大佬也发话了，指点我们这两种方式都不是很好，让我们去看一下尾递归(实话说，我早就还给大学老师了=。=)
言归正传，开始干活。
------------------------------假装我是分割线---------------------------
如题：

我最开始的解法是直接递归

function sum(n){
        if(n==0){
            return 0;
        }else if(n==1) {
            return 1;
        }
        else{
            return (arguments.callee(n-1)+arguments.callee(n-2));
           }
      }

这个实现简单明了就是执行速度太慢了，因为编译器是以如下方式进行计算的（例如计算Fib（6））：

Fib(6) = Fib(5) + Fib(4);
         = Fib(4) + Fib(3) + Fib(3) + Fib(2);
         = Fib(3) + Fib(2) + Fib(2) + Fib(1) + Fib(2) + Fib(1) + Fib(2);
         = Fib(2) + Fib(1) + Fib(2) + Fib(2) + Fib(1) + Fib(2) + Fib(1) + Fib(2);
         = 8

从上面的递归展开式可以看出Fib(4),Fib(3)都被计算了2次，而且递归函数以2的指数增长。所以当计算到30时就变得非常慢。(当然这都是后话了，我开始哪里知道这么多~)

后来群里同学说使用闭包会比直接递归快，那我就试着用了下闭包；

var sum    =(function (){
        return function(n){
            if(n==0 || n==1){
                return n;
            }else{
                return (sum(n-1)+sum(n-2));
               }
        }})();

使用了闭包确实感觉自己吊了一点啊，整个人都萌萌哒，而且后面测试速度也证实了比我原来的好一点。

后面，大佬指导说直接递归和闭包都很影响性能（我实现出来都很不容易呀），告诉我们使用尾递归会极大的提高性能，好吧，我只好去查查什么是尾递归了，看了几个demo我写了如下代码：

    function sum(n,a,b){
             if (n ==0 ){
                return a;
             }
             else{
                 return sum(n-1, b, a +b);
            }
    }

具体执行过程我后面会给传送门，我也是从那看到的。

---------------------------------分割线又来了--------------------------------

接下来我们来对比一下代码性能

直接递归的耗时

分别比较了n为30,33,35的值时候的耗时，图中有两个数字，上面的是计算得到的斐波那契数列结果，下面是耗时，单位是毫秒。

闭包

尾递归

循环

迭代实现

//使用Java方式，主要是看实现思想
public static long fibo3(long n){    
    if(n<2) return n;    
    long pre=1,prepre=1,ret=0;    
    for(int i=2;i
从图中我们可以很明显的看出，使用尾递归计算斐波那契数列性能完胜直接递归和闭包，特别是当数值比较大的时候，尾递归的作用就越明显。循环的方式性能也很好，其实实现斐波那契数列方式多种多样，真的只是你想不到而已，好了，收工吃饭！
最后想看尾递归算法的可以看这里：尾递归实现斐波那契

云服务器 GPU云服务器波那契数列简单的html作业 asp net的作业引发了

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/89888.html

算法记录 >> 斐波那契数列

摘要：今天去面试笔试题斐波那契数列实现，虽然很简单。回来想想既然算法这么重要那就从这个开始来记录自己的算法库吧。在数学上，斐波纳契数列以如下被以递归的方法定义，，。斐波拉契算法规律很简单，，观察下数列值就很容易总结出来了。一、写在前面算法这块对于大多数程序员（包括我）来说可能都是一个薄弱的地方，如何弥补尼？每个人都知道那就是学习、特别是算法没有任何捷径可走。在这记录平时自己工作和生...

robin 2019-08-16 17:52 评论0 收藏0
太原面经分享：如何用js实现返回斐波那契数列的第n个值的函数

摘要：那其实这个问题还可以换个问法实现一个函数，输入一个数字能返回斐波那契数列的第个值。文章预告更多的前端面试分享我都会第一时间更新在我的公众号闰土大叔里面，欢迎关注面试攒经验，lets go！值此高考来临之际，闲不住的我又双叒叕出发去面试攒经验了，去了公司交待一番流程后，面试官甩给了我一张A4纸，上面写着一道js算法笔试题（一开始我并不知道这是在考察js算法），上面写着1、1、2、3、...

Galence 2019-08-26 12:01 评论0 收藏0
js实现斐波那契数列

摘要：实现斐波那契数列斐波那契数列最大数斐波那契数列由和开始之后的斐波那契数列系数就由之前的两数相加。换个写法，用箭头函数最大数斐波那契数列由和开始 js实现斐波那契数列 // 斐波那契数列 let max=10000; // 最大数 let arr=[0,1]; // 斐波那契数列由 0 和 1 开始 // 之后的斐波那契数列系数就由之前的两数相加。 ...

notebin 2019-08-23 15:42 评论0 收藏0
使用js实现斐波那契数列

摘要：前言前几天面试被问到了斐波那契数列的实现以及优化的问题，当时现场卡了挺久的，现在进行一下总结使用实现。题目介绍斐波那契数列又被称为黄金分割数列，指的是这样的一个数列，它有如下递推的方法定义是正整数，请使用实现斐波那契函数。前言前几天面试被问到了斐波那契数列的实现以及优化的问题，当时现场卡了挺久的，现在进行一下总结（使用js实现）。题目介绍斐波那契数列又被称为黄金分割数列，指...

alexnevsky 2019-08-26 13:36 评论0 收藏0
js 实现斐波那契数列(数组缓存、动态规划、尾调用优化)

摘要：根据该规则，返回第个斐波那契数。尾递归函数调用自身，称为递归。一个前端眼中的斐波那契数列解斐波那契数列的实用解法调用栈尾递归和手动优化尾调用优化译我从用写斐波那契生成器中学到的令人惊讶的件事斐波那契数列是以下一系列数字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在种子数字 0 和 1 ...

赵连江 2019-08-23 11:38 评论0 收藏0