斐波那契数的递归与非递归实现

斐波那契数计算的方法一般采用递归的方法，返回类型一般采用int或者long类型。在这种条件下会产生两个问题：
1. 效率问题，比如计算第46个斐波那契数值，需要6秒多。计算第50个斐波那契数需要一分钟左右，后面越来越难以想象。
2. 数值溢出问题。返回类型采用int类型的话，最多可以计算出f(46) = 1836311903, 计算f(47)时就会产生溢出。返回类型采用long类型的话，最多可以计算出f(92) = 7540113804746346429, 计算f(93)时就会产生溢出。

解决效率问题的方法就是采用非递归的方式。
非递归的思想 当n =1 或者 n=2的时返回1。当n大于2时，通过for循环改变值来实现。
如：初始化两个变量num1 = 1, num2 =1，把它们想象成f(1) 和 f(2)，在循环体中改变它们对应的值。把num2的值表示成num1, num2的值用num1与num2的和来表示。这样一来， num2就是f(n)的结果。



非递归实现比较快，一般在0.0秒级。

解决数值溢出的方法是采用BigInteger来实现。

f(500) = 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125

Time Elasped:0.0秒

递归与非递归的代码如下：

import java.math.BigInteger;

public class Fibonacci {

	/**
	 * 
	 * 采用递归方法实现
	 * 
	 * 用int类型的话，最多可以计算出f(46) = 1836311903, 计算f(47)时就会产生溢出。
	 * f(42) = 267914296
	 * f(43) = 433494437
	 * f(44) = 701408733
	 * f(45) = 1134903170
	 * f(46) = 1836311903
	 * f(47) = -1323752223
	 * 

	 * 
	 * @return 返回第n个斐波纳契数
	 */
	public int fibonacci1(int n) {
		if (1 == n || 2 == n) {
			return 1;
		} else {
			return fibonacci1(n - 1) + fibonacci1(n - 2);
		}
	}

	/**
	 * 
	 * 采用非递归方法实现，效率比递归方法要高很多。
	 * 
	 * 用int类型的话，最多可以计算出f(46) = 1836311903, 计算f(47)时就会产生溢出。
	 * f(42) = 267914296
	 * f(43) = 433494437
	 * f(44) = 701408733
	 * f(45) = 1134903170
	 * f(46) = 1836311903
	 * f(47) = -1323752223
	 * 

	 * 
	 * @return 返回第n个斐波纳契数
	 */
	public int fibonacci2(int n) {
		if (1 == n || 2 == n) {
			return 1;
		}
		int num1 = 1;
		int num2 = 1;
		int temp = 0;
		for (int i = 2; i < n; i++) {
			temp = num2;
			num2 += num1;
			num1 = temp;
		}
		return num2;
	}

	/**
	 * 
	 * 采用递归方法实现
	 * 
	 * 用long类型的话，最多可以计算出f(92) = 7540113804746346429, 计算f(93)时就会产生溢出。
	 * f(90) = 2880067194370816120
	 * f(91) = 4660046610375530309
	 * f(92) = 7540113804746346429
	 * f(93) = -6246583658587674878
	 * 

	 * 
	 * @return 返回第n个斐波纳契数
	 */
	public long fibonacci3(int n) {
		if (1 == n || 2 == n) {
			return 1;
		} else {
			return fibonacci3(n - 1) + fibonacci3(n - 2);
		}
	}

	/**
	 * 
	 * 采用非递归方法实现，效率比递归方法要高很多。
	 * 
	 * 用long类型的话，最多可以计算出f(92) = 7540113804746346429, 计算f(93)时就会产生溢出。
	 * f(90) = 2880067194370816120
	 * f(91) = 4660046610375530309
	 * f(92) = 7540113804746346429
	 * f(93) = -6246583658587674878
	 * 

	 * 
	 * @return 返回第n个斐波纳契数
	 */
	public long fibonacci4(int n) {
		if (1 == n || 2 == n) {
			return 1;
		}
		long num1 = 1;
		long num2 = 1;
		long temp = 0;
		for (int i = 2; i < n; i++) {
			temp = num2;
			num2 += num1;
			num1 = temp;
		}
		return num2;
	}
	
	/**
	 * 
	 * 采用非递归的方式来实现，同时采用BigInteger来实现。
	 * 
	 * 

	 * @return 返回第n个斐波纳契数
	 */
	public BigInteger populateWithoutRecursion(int n){
		if (1 == n || 2 == n) {
			return new BigInteger("1");
		}
		BigInteger num1 = new BigInteger("1");
		BigInteger num2 = new BigInteger("1");
		BigInteger temp = new BigInteger("0");
		for(int i=2;i<n;i++){
			temp = num2;
			num2 = num2.add(num1);
			num1 = temp;
		}
		return num2;
	}
	
	public static void main(String[] args) {
		Fibonacci f = new Fibonacci();
		long start = System.currentTimeMillis();
		System.out.println( f.populateWithoutRecursion(500));
		long end = System.currentTimeMillis();
		System.out.println("Time Elasped:" + (end - start)/1000.0 + "秒");
	}
	
	
}

评论

1 楼 zenghuiss 2015-07-24  

非递归时，要<=n才行哦