js斐波那契数列递归算法_php斐波那契数列递归算法

js斐波那契数列递归算法_php斐波那契数列递归算法斐波那契数列(Fibonaccisequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(LeonardoFibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……从数列可以看出,从第三项开始,每一项都是前两项的和,f(n)=f(n-1)+f(n-2)那么用js怎么求斐波那契数列第n项的值呢?1.普通递归计算:functionfibonacci(n){if(n==1||n==2)retu

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……从数列可以看出,从第三项开始,每一项都是前两项的和,f(n) = f(n-1) + f(n-2)
那么用js怎么求斐波那契数列第n项的值呢?

1.普通递归计算:

function fibonacci(n){ 
   
    if(n == 1||n == 2) return 1
    return fibonacci(n - 1) + fibonacci(n - 2)
}
fibonacci(5)
// > 5
fibonacci(50)
// > 卡住了

当n等于1或者n等于2的时候,直接返回1,当n大于2的时候,就递归函数,每次返回前两个函数的结果,这就是最基础的斐波那契数列递归算法。但是大家都知道,函数运行的时候,会被放入函数执行栈运行,如果内部还有函数,那么就会继续入栈,直到最内部函数,然后再一个个出栈,直到栈清空,取得结果。把上边的函数放入控制台运行,就会发现,当n比较大的时候,大概50以上函数栈就会非常大,以至于计算机几分钟内不能算出结果。那么可想而知,当n越来越大的时候,用这个函数,几乎不能算出结果了。所以我们可以用尾递归去优化它。

2:尾递归计算:

function fibonacci(n,a1 = 1,a2 = 1){ 
   
    if(n == 1||n == 2) return a2
    return fibonacci(n - 1,a2,a1 + a2)
}
fibonacci(5)
>> 5
fibonacci(50)
>> 12586269025

从这个函数可以看出,我们的递归每次返回的时候,我们把计算结果传入下一个函数,return放在最后,只返回一个函数调用,那么上一个函数其实是已经结束了函数的调用的,此时他会从栈中弹出,那么函数执行栈始终只有一个。把这段函数复制到控制台运行,可以看出,即便是n很大,也能很快算出结果。
细心的同学可能发现了,这其实就是一个迭代啊,只不过把迭代计算放入了递归函数的参数中。

3:迭代计算:

function fibonacci(n){ 
   
    if(n == 1||n == 2) return 1
    let a1 = 1,a2 = 1
    for(i = 2;i < n;i++){ 
   
        [a1,a2] = [a2,a1+a2]
    }
    return a2
}
fibonacci(5)
>> 5
fibonacci(50)
>> 12586269025

普通的迭代计算,也可以很快计算出结果。

4:缓存计算结果:

function fibonacci(n){ 
   
    if(n == 1||n == 2) return 1
    if(!fibonacci[n+'']){ 
   
        fibonacci[n+''] = fibonacci(n - 1) + fibonacci(n - 2)
    }
    return fibonacci[n+'']
}
fibonacci(5)
>> 5
fibonacci(50)
>> 12586269025
fibonacci(100)
>> 354224848179262000000

这里咱们用缓存计算结果修改第一个普通递归,刚才分析了,普通递归因为函数执行栈太大以至于难以计算出n很大的结果,那么咱们用函数的属性,存放那些已经计算过的结果,如果有,就直接返回,没有的话,给对应的属性 n 赋值再返回,也可以很快计算出结果。但是给函数添加了很多属性,毕竟是占了不少空间,这属于用空间换时间的算法。具体用不用,就取决于使用者的空间成本和时间成本了。

当然,还有一些其他的算法,这里就不一一列举了。有更好算法的同学欢迎评论区留言。

上一篇:小数点保留两位的js正则表达式
下一篇:vue3 setup如何使用emit?

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/185930.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • opencv图像角点提取

    opencv图像角点提取opencv角点检测(二)改进的Harris角点检测算法harris角点检测算法的结果一定程度上取决于系数k,有人对Harris的角点检测算法进行了改进,直接利用像素点协方差矩阵的特征值提取角点。而且不在进行非极大值抑制,而是采用一种容忍距离的形式,在角点的一定范围内只有一个角点。具体原理:首先计算图像每个像素点的协方差矩阵,并求取对应的特征值,将最小的特征值最大的那个像素点作为第

  • tomcat日志详解[通俗易懂]

    tomcat日志详解[通俗易懂]文章目录tomcat日志配置tomcat日志文件详解catalina.outcatalina.YYYY-MM-DD.loglocalhost.YYYY-MM-DD.loglocalhost_access_log.YYYY-MM-DD.txthost-manager.YYYY-MM-DD.logmanager.YYYY-MM-DD.log访问日志详细配置tomcat日志文件切割tomcat日志配…

  • 二叉树的5个重要性质「建议收藏」

    二叉树的5个重要性质「建议收藏」1.在二叉树的第i层上最多有2 i-1 个节点。(i>=1) 用归纳法证明:归纳基:i=1层时,只有一个根结点,          2i-1=20=1;归纳假设:假设i=k时,命题成立;归纳证明:二叉树上每个结点至多有两棵子树,则第k+1层的结点数最多为2k-12=2k+1-1。

  • 用vb.net实现写字板程序报告(二)

    用vb.net实现写字板程序报告(二)所有源代码均在这里下载:http://www.up2e.com/resource.php 用vb.net实现写字板程序报告(二)–byzigz(LuHai)luluhai@eastday.com 3)           状态栏的隐藏就是在“查看”菜单中有个check按钮,当checked=true时点击它状态栏就隐藏,反之就取消隐藏。PrivateSubmSt

  • 【动画教程】真封神南极服务端2.52架设第四集「建议收藏」

    【动画教程】真封神南极服务端2.52架设第四集「建议收藏」官方网站www.zfs2014.com动画名称:真封神南极服务端2.52架设第四集主讲人:diablo2208教程下载地址:http://pan.baidu.com/s/1bnf9EkZ

  • mysql数据库日志存储位置_MySQL数据库之mysql日志文件在哪 如何修改MySQL日志文件位置…「建议收藏」

    mysql数据库日志存储位置_MySQL数据库之mysql日志文件在哪 如何修改MySQL日志文件位置…「建议收藏」本文主要向大家介绍了MySQL数据库之mysql日志文件在哪如何修改MySQL日志文件位置,通过具体的内容向大家展现,希望对大家学习MySQL数据库有所帮助。MySQL日志文件相信大家都有很多的了解,MySQL日志文件一般在:/var/log/mysqld.log,下面就教您修改MySQL日志文件位置的方法,供您参考。今天需要改MySQL日志文件的位置,发现在/etc/my.cnf中怎么也改不…

    2022年10月14日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号