运用斐波那契数列浅谈递归与迭代算法

首先放上一个数学问题(一个大学学妹问的)

典型的斐波那契数列问题

递归

首先由两种解决方式,第一种会想到递归,因为这样代码逻辑简单所以我第一感觉也是用递归算法于是写了下列测试代码计算 f(1-100) 得数

 public static int f(int n){
        int y=0;
        if (n==1||n==3){
           y=1;
        }else if(n==2){
            y=0;
        }else if(n>3){
           y=f(n-1)-2*f(n-2)+f(n-3);
        }
        return y;
    }

逻辑简单粗暴代码通俗易懂,但是当我主程序调用的时候问题就来了,由于调用次数太多…导致堆栈溢出程序崩溃于是把数调小测试了时间

测了从1-35的结果程序跑了8028ms 后面每增一个数就会指数级增长可怕的很,终于找到程序崩溃的原因了原来是递归本身算法问题每个递归调用都触发另外两个递归调用，而这两个调用的任何一个又将调用另外连个递归调用，这样冗余计算的增量是非常快的，例如图：

于是乎想到了第二种思路迭代 ,

迭代

迭代的思想就是不断地用变量的旧值递推新值的过程。迭代法相对于递归效率要高，因为节省了重复计算,逻辑代码就比较复杂了
(逻辑想了有一会儿,数学还给老师了啊啊啊)

public static int f(int n){
        //假设开始时f1=1,f2=0,f3=1
        int f1 = 1;
        int f2 = 0;
        int f3 = 1;
        int currentNum=0;
        if(n==1||n==3){
            return 1;
        }else if (n==2){
            return 0;
        }
        for (int i=4;i<=n;i++){
            currentNum=f3-2*f2+f1;
            f3=f2;
            f2=f1;
            f1=currentNum;
        }
        return currentNum;
    }

那用递归的方法效率咋样呢?我们来试一下话不多说直接循环1-100(递归是1-35)

可以看到只运行了7ms WTF!!!好了问题完美解决剩下的只是数据处理问题
所以说递归迭代看情况使用
当然还有递归优化问题,后续有机会做深入研究
参考资料https://blog.****.net/qq_37818095/article/details/81944809
https://blog.****.net/tanjie_123/article/details/53005466
https://www.cnblogs.com/wdxg0103/p/8629198.html