斐波那契数列（递归与非递归算法）

一时失言乱红尘 2022-09-19 15:29 248阅读 0赞

斐波那契数列，又称[黄金分割][Link 1]数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N\*）在[现代物理][Link 2]、准[晶体结构][Link 3]、化学等领域，斐波纳契数列都有直接的应用。

学习递归算法的时候一般都会了解这个数列，以此作为例子来研究。

我学习算法这些也都是自学，所以第一次接触递归并不是这个例子，而且我到现在也不是很了解递归算法的过程。所以，以致我接触到斐波那契数列的时候直接用循环的方式写出来了，之后的学习的发现这样的速度比递归实现快，是对递归算法速度的改进算法，顿时对自己不熟悉递归而感到也不是那么次啊......

下面给出递归的算法：

package org.zsl.algorithm.fibonacci;
    
    public class Fibonacci1 {
    	//斐波那契数列中的递归	
    	public static void main(String[] args) {
    		System.out.println(fibonacci(40));
    	}
    	//递归调用
    	public static int fibonacci(int n){	//此算法在N=40时出现明显卡顿
    		if(n==0) return 0;
    		if(n==1) return 1;
    		return fibonacci(n-1)+fibonacci(n-2);
    	}
    }

这是我自己写的非递归的算法：

package org.zsl.algorithm.fibonacci;
    
    public class Fibonacci2 {
    	public static void main(String[] args) {
    		System.out.println(fibonacci2(46));
    	}
    	public static int fibonacci2(int N){	//此算法速度较快，N=46时也不卡顿，N=47时超过了int范围
    		
    		int[] arr = new int[N+1];	//数组从0开始，若想要一个数组有a[9],在声明时必须是int[] a = new int[10];这样才会有a[9]
    		arr[0] = 0 ;
    		arr[1] = 1 ;
    		if( N==0 ) return 0;
    		if(N==1) return 1;
    		if(N>1){
    			for(int i = 2;i<=N;i++)
    				arr[i] = arr[i-1]+ arr[i-2];
    		}
    		return arr[N];
    		
    	}
    }

[Link 1]: http://baike.baidu.com/view/1816.htm
[Link 2]: http://baike.baidu.com/view/4375609.htm
[Link 3]: http://baike.baidu.com/view/591665.htm