JS用For循环实现斐波那契数列(及尾递归优化)

斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N）*

递归实现

function Fibo(n) {if(n <= 0) {return -1; //输入的n不合法，返回-1}if(n <= 2) {return 1; // 第一项和第二项为1} else {return Fibo(n-2) + Fibo(n-1); // 从第三项开始等于前两项的和}}

递归非常占用内存，所以不能进行多次递归调用，可以用for循环改进

for循环实现

因为这里面，我们从前面依次往后累加，所以需要定义三个变量， n_value = pre + next

function Fibo(n) {if(n <= 0) {return -1;}if(n <= 2) {return 1;}let pre = 1; //第一次循环pre是f(1)也就是1let next = 1; //第一次循环next是f(2)也就是1let n_value = 0; // 保存f(n)的值for(let i = 3; i <= n; i++) {n_value = pre + next; //每一次循环n_value就是前两个数的和pre = next; // 然后把next赋值给prenext = n_value; //把新的n_value的值赋值给next} return n_value;}

尾递归优化

尾递归，函数最后一步调用自身

function Fibo(n, a1=1, a2=1) {if(n<=2) {return a2;}return Fibo(n-1, a2, a1+a2);}