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)


相关推荐

  • icp光谱分析仪_个人icp备案

    icp光谱分析仪_个人icp备案输入44 21 2 4 84 0100 99 98 972 210000 100005 30 0 0 0 1696RichmanImpossible代码#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N = 1e5 + 10;int a[N];int main(){ int T; cin>>T; while(T -..

  • 均值漂移(Meanshift)算法

    均值漂移(Meanshift)算法均值漂移(Meanshift)1.均值漂移的基本概念:沿着密度上升方向寻找聚簇点设想在一个有N个样本点的特征空间初始确定一个中心点center,计算在设置的半径为D的圆形空间内所有的点(xi)与中心点center的向量计算整个圆形空间内所有向量的平均值,得到一个偏移均值将中心点center移动到偏移均值位置重复移动,直到满足一定条件结束2.均值漂移运算:

  • RapidXml使用方法

    RapidXml使用方法一、写xml文件#include#include”rapidxml/rapidxml.hpp”#include”rapidxml/rapidxml_utils.hpp”#include”rapidxml/rapidxml_print.hpp”usingnamespacerapidxml;intmain(){ xml_document<>doc;

  • 软件安装:mariadb安装教程

    软件安装:mariadb安装教程MySQL被Oracle收购后,出现了一个基于MySQL的开源数据库Mariadb。下面介绍一下Mariadb在windows7上的安装过程。下载时,提示要注册,可以选择不注册。真是跟MySQL的一样啊。安装教程连接:https://jingyan.baidu.com/article/f96699bb00ce67894e3c1b9a.html…

  • shell中if语句_shell脚本if判断

    shell中if语句_shell脚本if判断提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档文章目录一、if语句1.if单分支判断2.if双分支判断3.if多分支判断总结提示:以下是本篇文章正文内容,下面案例可供参考一、if语句1.if单分支判断●当“条件成立”时执行命令序列●否则不执行任合操作语法格式♦if空格条件测试then命令序列fiif加空格加一个条件测试,如果这个条件测试结果为真那么就执行then后面的命令序列,这个命令序列可以是一条命令也可以是多条命令只要条件测试为真,.

  • IDEA使用教程_intellij idea使用教程

    IDEA使用教程_intellij idea使用教程idea启动后会在cpan当前用户下生成一个C:\Users\Crystal.IntelliJIdea2018.1文件夹,这个文件夹里面有两个子文件夹config和system。删除这两个文件夹,idea在启动时候会重新配置。idea的project类似于eclipse的workspace;idea的modue类似于eclipse的project;配置都是在setti…

    2022年10月13日

发表回复

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

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