斐波那契数列（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？
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/185930.html原文链接：https://javaforall.net
