常用的计算斐波那契数列的方法分为两大类：递归和循环。

递归

方法一：普通递归

代码优美逻辑清晰。但是有重复计算的问题，如：当n为5的时候要计算fibonacci(4) + fibonacci(3)，当n为4的要计算fibonacci(3) + fibonacci(2) ，这时fibonacci(3)就是重复计算了。运行 fibonacci(50) 会出现浏览器假死现象，毕竟递归需要堆栈，数字过大内存不够。

复制
1function fibonacci(n) {
2    if (n == 1 || n == 2) {
3        return 1
4    };
5    return fibonacci(n - 2) + fibonacci(n - 1);
6}
7fibonacci(30)

方法二：改进递归-把前两位数字做成参数避免重复计算

复制
1function fibonacci(n) {
2    function fib(n, v1, v2) {
3        if (n == 1)
4            return v1;
5        if (n == 2)
6            return v2;
7        else
8            return fib(n - 1, v2, v1 + v2)
9    }
10    return fib(n, 1, 1)
11}
12fibonacci(30)

方法三：改进递归-利用闭包特性把运算结果存储在数组里，避免重复计算

复制
1var fibonacci = function () {
2    let memo = [0, 1];
3    let fib = function (n) {
4        if (memo[n] == undefined) {
5            memo[n] = fib(n - 2) + fib(n - 1)
6        }
7        return memo[n]
8    }
9    return fib;
10}()
11fibonacci(30)

方法四：改进递归-摘出存储计算结果的功能函数

复制
1var memoizer = function (func) {
2    let memo = [];
3    return function (n) {
4        if (memo[n] == undefined) {
5            memo[n] = func(n)
6        }
7        return memo[n]
8    }
9};
10var fibonacci=memoizer(function(n){
11    if (n == 1 || n == 2) {
12        return 1
13    };
14    return fibonacci(n - 2) + fibonacci(n - 1);
15})
16fibonacci(30)

循环

方法一：普通for循环

复制
1function fibonacci(n) {
2    var n1 = 1, n2 = 1, sum;
3    for (let i = 2; i < n; i++) {
4        sum = n1 + n2
5        n1 = n2
6        n2 = sum
7    }
8    return sum
9}
10fibonacci(30)

方法二：for循环+解构赋值

复制
1var fibonacci = function (n) {
2    let n1 = 1; n2 = 1;
3    for (let i = 2; i < n; i++) {
4        [n1, n2] = [n2, n1 + n2]
5    }
6    return n2
7}
8fibonacci(30)

本答案由“前端面试题宝典”收集整理，PC端访问请前往： https://fe.ecool.fun/