斐波那契数列--递归与非递归实现

ゝ一纸荒年。 2022-05-23 05:40 170阅读 0赞

**初识斐波那契数列：**  
**斐波那契数列（Fibonacci sequence）**，又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0，1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N\*）。  
**代码实现1—递归：**

public class FibSeq{
        public static int fibSeq(int n){
            if(n<0){
                throw new IllegalArgumentException("the param is less than 0");
            }
            if(n==0)
                return 0;
    
            if(n==1)
                return 1;
            return fibSeq(n-1);+fibSeq(n-2);
        }
        public static void main(String[] args) {
            //测试前10个
            for(int i=0;i<10;i++){
            System.out.print(fibSeq(i)+" ");
            }
    
        }
    }

结果：  
![这里写图片描述][70]  
**代码实现1—普通循环：**

public class FibSeq{
        public static int FeiBo1(int n){
            if(n<0){
                throw new IllegalArgumentException("the param is less than 0");             
            }
            if(n==0||n==1){
                return n;
            }
            /*int []res={0,1}; if(n<2) return res[n];*/
            int result=0;
            int fb0=0;
            int fb1=1;
    
            for(int i=2;i<=n;i++){
                result=fb1+fb0;
                fb0=fb1;//先把下一个元素赋值给下下个元素，如果先把result赋值给下一个元素fb1，
                //则会将fb1覆盖为result，当fb1在赋值给fb0时此时的fb0仍然是result的值
                fb1=result;
    
            }
            return result;
        }
        public static void main(String[] args) {
            //测试前10个
            for(int i=0;i<10;i++){
            System.out.print(FeiBo1(i)+" ");
            }
    
    }

结果：  
![非递归实现][70 1]  
**总结：**  
从代码量来看递归实现要简单的多，但随着数量n的增加，递归实现的时间复杂度也会随着指数级增加，这是因为递归实现不断的调用自己的字方法，中间会存在大量重复的元素，例如f(9)=f(8)+f(7),f(8)=f(7)+f(6),这两个递归下来就会产生相同的f(7),当f(7)继续调用时(f(7)=f(5)+f(6))，都会同时调用f(6)+f(5),,当n很大时，会产生大量的重复元素，继而会产生大量的重复的方法调用，而每一次方法的调用虚拟机都会在内存栈中重新分配空间以保存参数、返回地址和临时变量，而每个栈的容量是有限的，当递归调用层级太多时，会产生栈溢出，所以对于测试n=10,100,500,1000时普通循环的时间消耗要明显小于递归实现。对于n很大时应该采用普通循环来计算斐波那契数列的值。

[70]: /images/20220523/322d8f3f21164f22b8e196631fa0382e.png
[70 1]: /images/20220523/df91ac73f3c348d8a88927f28e2eea99.png