斐波那契数列

Love The Way You Lie 2022-11-19 04:15 233阅读 0赞

斐波那契数，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波那契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2，n∈N\*），用文字来说，就是斐波那契数列由 0 和 1 开始，之后的斐波那契数列系数就由之前的两数相加。

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

# 递归 #

## 方法一：普通递归 ##

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

function fibonacci(n) {
        if (n == 1 || n == 2) {
            return 1
        };
        return fibonacci(n - 2) + fibonacci(n - 1);
    }
    fibonacci(30)

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

尾递归：如果函数尾调用自身就成为尾递归

function fibonacci(n) {
        function fib(n, v1, v2) {
            if (n == 1)
                return v1;
            if (n == 2)
                return v2;
            else
                return fib(n - 1, v2, v1 + v2)
        }
        return fib(n, 1, 1)
    }
    fibonacci(30)

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

var fibonacci = function () {
        let memo = [0, 1];
        let fib = function (n) {
            if (memo[n] == undefined) {
                memo[n] = fib(n - 2) + fib(n - 1)
            }
            return memo[n]
        }
        return fib;
    }()
    fibonacci(30)

## 循环 ##

## 方法一：普通for循环 ##

function fibonacci(n) {
        var n1 = 1, n2 = 1, sum;
        for (let i = 2; i < n; i++) {
            sum = n1 + n2
            n1 = n2
            n2 = sum
        }
        return sum
    }
    fibonacci(30)

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

var fibonacci = function (n) {
        let n1 = 1; n2 = 1;
        for (let i = 2; i < n; i++) {
            [n1, n2] = [n2, n1 + n2]
        }
        return n2
    }
    fibonacci(30)

各种方法运行耗时如下图：普通递归>改进递归>for循环

![caaf29da8eec90cc6fdf43150b985375.png][]

[caaf29da8eec90cc6fdf43150b985375.png]: /images/20221022/a5975465a8c146b98da53ed2ceb93685.png