斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
前两项为1，从第三项起，每一项等于前两项的和，即F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
请用JS实现：输入斐波那契数列的项数，输出该项的值
方法1：递归
function fibonacci(n){ if(n==1||n==2){ return 1 }else{ return fibonacci(n-1)+fibonacci(n-2) } }
递归方式是大多数人的常规思路，但是使用递归求一个较大项的值十分耗费性能，不推荐使用！
console.time('fibo-runtime')console.log(fibonacci(50))console.timeEnd('fibo-runtime')12586269025 fibo-runtime: 131143.2421875ms
方法2：循环
function fibo—cycle(n){ var num1 = 1,num2 = 1,sum; for(var i = 3; i < n; i++){ sum = num1 + num2; //用sum累加前两个数之和 num1 = num2; num2 = sum; } if(n==1||n==2){ return 1 }else{ return sum } } console.log(fibo_cycle(5)) //5
方法3：数组
function fibo_arr(n){ var arr = [0,1,1] if(n<0){ throw new Error('输入的数字不能小于0') } if(n>=3){ for(var i = 3; i <= n; i++){ arr[i] = arr[i-1]+arr[i-2] } } return arr[n] }console.log(fibo_arr(5)) //5
方法4：闭包
function fibo(n){ if(n<0){ throw new Error('输入的数字不能小于0') } let arr = [0,1,1]; function recursion(n){ if(n<3){ return arr[n] } if(arr[n]!==undefined){ return arr[n] } let data = recursion(n-1)+recursion(n-2) arr[n] = data //将data保存，避免重复求值 return data } return recursion(n)} console.log(fibo_arr(5)) //5
转载于:https://www.cnblogs.com/AIonTheRoad/p/11362500.html
