Open cobish opened 5 years ago
// 利用 Generator 函数和for...of循环,实现斐波那契数列
function* fibonacci() {
let index = 0; // ==> action : {index, value} Or [index, value]
let [prev, curr] = [[0], [1, index++]];
for (;;) {
yield curr;
[prev, curr] = [curr, [prev[0] + curr[0], index++]];
}
}
function getFibonacci(index) {
for (let [n, i] of fibonacci()) {
// 可以指定第n项, 也可以指定小于1000的最大斐波拉契数
if (i >= index) {
console.log(n, i);
return n;
break;
}
}
}
function* fibonacci(n) {
for(let [prev, curr] = [0, 1], index = 0; index <= n; index++) {
yield curr;
[prev, curr] = [curr, prev + curr];
}
}
// 调用, rest可以得到斐波那契数组
[...fibonacci(n)]
什么是斐波那契数列?
斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……
在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=1,F(1)=1, F(n)=F(n-1)+F(n-2)(n>2,n∈N*)
实现方式
实现的主要思路为 F(n)=F(n-1)+F(n-2),即后面一个数是由前面两个数相加得来。
循环实现
递归实现
递归实现起来更加的简洁。
这个方法算是代码最少也容易理解,但是当 n 较大时很快产生栈溢出,引发原因是“调用帧”过多。
主要是因为执行上下文栈里压入过多的函数,但又没及时弹出,解决方案可以使用尾调用(思路跟循环很像)。
递归实现的比较
前面用到了两种递归的方式,就用执行上下文栈来比较一下它们吧。
第一种递归方法的执行上下文栈的变化为:
第二种递归方法(尾调用)的执行上下文栈的变化为:
可以看到第二种递归方法用完就弹出,所以不会导致栈溢出。
尾递归可以参考:JavaScript专题之递归。