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)


相关推荐

  • uC/OS-II中,各个任务间可以共享任务堆栈_什么是多任务系统

    uC/OS-II中,各个任务间可以共享任务堆栈_什么是多任务系统想让uC/OS-Ⅱ管理用户的任务,用户必须要先建立任务。用户可以通过传递任务地址和其它参数到以下两个函数之一来建立任务:OSTaskCreate()或OSTaskCreateExt()。OSTaskCreate()与uC/OS是向下兼容的,OSTaskCreateExt()是OSTaskCreate()的扩展版本,提供了一些附加的功能。用两个函数中的任何一个都可以建立任务。  任务可以在多任…

  • android开发之蓝牙配对连接的方法「建议收藏」

    新年第一篇。最近在做蓝牙开锁的小项目,手机去连接单片机总是出现问题,和手机的连接也不稳定,看了不少蓝牙方面的文档,做了个关于蓝牙连接的小结。在做android蓝牙串口连接的时候一般会使用BluetoothSocket tmp = null;// Get a BluetoothSocket for a connection with the// given BluetoothDevi

  • YIQ颜色空间_简述RGB颜色

    YIQ颜色空间_简述RGB颜色首先,我们先来了解下有关颜色的基本概念一、色彩的基本概念1、彩色的三要素亮度:即人眼对光的明亮程度的感受。色调:人眼能看到的颜色种类,与光的波长有关饱和度:颜色深浅程度。与各种颜色混入白光的比例有关。以上色调+饱和度=色度2、三基色原理三基色可以通过适当比例的混合组成自然界中任何一种颜色由于人眼对于红绿蓝三种色光最为敏感,并且由这三种颜色能组成的颜色范围最广,故一般选用…

    2022年10月28日
  • ModelMap的用法

    ModelMap的用法ModelMap对象主要用于传递控制方法处理数据到结果页面,也就是说我们把结果页面上需要的数据放到ModelMap对象中即可,他的作用类似于request对象的setAttribute方法的作用,用来在一个请求过程中传递处理的数据。通过以下方法向页面传递参数:addAttribute(Stringkey,Objectvalue);在页面上可以通过el变量方式$key或者bboss的一系列数…

  • 视觉SLAM——特征点法与直接法对比以及主流开源方案对比 ORB LSD SVO DSO

    视觉SLAM——特征点法与直接法对比以及主流开源方案对比 ORB LSD SVO DSO单目视觉SLAM可以根据其前端视觉里程计或是后端优化的具体实现算法进行分类:前端可以分为特征点法与直接法,后端可以分为基于滤波器和基于非线性优化。其中在后端上目前已经公认基于非线性优化的方法在同等计算量的情况下,比滤波器能取得更好的结果。而前端的两种方法则各有优劣。本文将具体分析直接法相较于特征点法的优劣处,并具体介绍目前主流的开源方案,以供大家参考。

  • android开发之Notification_通知栏消息「建议收藏」

    Notification简介  Notification看名字就知道,是一个和提醒有关的东西,它通常和NotificationManager一块使用。具体来说,其主要功能如下。  1.NotificationManager和Notification用来设置通知  通知的设置等操作相对比较简单,基本的使用方式就是新建一个Notification对象,设置好通知的各项参数,然后使用系统后台

发表回复

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

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