「Java」斐波那契数列

🍑1.斐波那契数列是什么

斐波那契数列（Fibonacci sequence），又称数列，以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

🍑2.使用递归完成斐波那契数列

public static int fib(int n){
        if(n==1||n==2){
            return 1;
        }else{
            int tmp = fib(n-1)+fib(n-2);
            return tmp;
        }
    }

我们先让n=3开始，可以看出，当n=3时，tmp = fib(n-1)+fib(n-2)，即tmp = 1 + 1，下面的数依此类推。我们会发现，当n大于2时，程序就会进行一次递归，可能有人听不明白，所以我将图画了出来👇

但是运用递归来求斐波那契数列也会出现一个问题，当我们使用一次递归时，即再次调用了自身的函数，那么它会在寄存器中为我们新的一次调用开辟一个栈，这么看来，如果说我们这个n足够的大，就会开辟出很多个栈，那就会相当占内存。所以我们采用循环赋值的方式来简化它。

🍑3.循环赋值实现斐波那契数列

public static int fib2(int n){
        if(n==1&&n==2){
            return 1;
        }
        int f1 = 1;
        int f2 = 1;
        int f3 = 0;
        for (int i = 0; i < n-2; i++) {
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }

在这里我们利用循环，让f3 = f1 + f2，再将f2的值给f1，最后把f3的值给f2。这样就可以不用开辟一个新的栈，省下很多空间。