Java之递归和迭代用法

斐波那契数列的求和示例

package com.cxl.algorithm;

/**
 * 斐波那契数列
 *
 */
public class FibonacciSequenceTest {
	private static final int a1 = 1;//第一项默认值
	private static final int a2 = 2;//第二项默认值
	
	public static void main(String[] args) {
		//递归
		System.out.println("递归求和：" + FibonacciSequenceTest.getSumByFibonacciSequence(45));
		//迭代
		System.out.println("迭代求和：" + FibonacciSequenceTest.getSumByNonRecursive(45));
	}
	/**
	 * 斐波那契数列求和：迭代
	 * @return
	 */
	public static int getSumByNonRecursive(int n) {
		long startTime = System.currentTimeMillis();
		if(n == 1) {
			return a1;
		}
		int sum = a1 + a2;
		if(n == 2) {
			return sum;
		}
		int firstNum = a1;
		int secondNum = a2;
		int lastNum = 0;
		for(int i = 3; i <= n ;i++) {
			//迭代关系(an = an-2 + an-1; an-2=an-1; an-1=an;)
			lastNum = firstNum + secondNum;
			firstNum = secondNum;
			secondNum = lastNum;
			sum += lastNum;
		}
		System.out.println("迭代求和耗时：" + (System.currentTimeMillis() - startTime) + "ms");//0ms
		return sum;
	}
	
	/**
	 * 斐波那契数列前n项和（sn = a1 + a2+...+ an) 递归
	 * @return
	 */
	public static int getSumByFibonacciSequence(int n) {
		long startTime = System.currentTimeMillis();
		if(n == 1) {
			return a1;
		}
		int sum = 1;
		int lastNum = 0;
		for(int i = 2; i <= n; i++) {
			lastNum = FibonacciSequenceTest.getLastNum(i);
			sum += lastNum;
		}
		System.out.println("递归求和耗时：" + (System.currentTimeMillis() - startTime) + "ms");//14839ms
		return sum;
	}
	
	/**
	 * 递归：第n项的值（递推公式：an = a(n - 1) + a(n - 2)）
	 * 1 2 3 5 8 13 21
	 * @param n
	 * @return
	 */
	public static int getLastNum(int n) {
		if(n == 1) {
			return a1;
		}
		if(n == 2) {
			return a2;
		}
		int lastListNum = getLastNum(n - 1) + getLastNum(n - 2);
		return lastListNum;
	}
}

数列求和：1 + 1/2! + 1/3! + 1/4! + 1/5! + ... + 1/50! 

package com.cxl.algorithm;

public class SquenceTest {

	/**
	 * 求和：1 + 1/2! + 1/3! + 1/4! + 1/5! + ... + 1/50!
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println("递归求和：" + SquenceTest.getSquenceSum(50));
		System.out.println("迭代求和：" + getSequenceSumByInterator(50));
	}
	
	/**
	 * 递归求和
	 * @param n
	 * @return
	 */
	public static double getSquenceSum(int n) {
		long startTime = System.currentTimeMillis();
		if(n == 1) {
			return 1d;
		}
		double sum = 1d;
		double a = 1d;
		for(int i = 2; i <= n; i++) {
			long num = getSquenceValueByRecurvise(i);
			sum += a / num;
		}
		System.out.println("递归求和耗时：" + (System.currentTimeMillis() - startTime) + "ms");//0ms
		return sum;
	}
	
	/**
	 * 递归方式
	 * @param n
	 * @return
	 */
	public static long getSquenceValueByRecurvise(int n) {
		if(n == 1) {
			return 1;
		}
		long squenceValue = n * getSquenceValueByRecurvise(n-1);
		return squenceValue;
	}
	
	/**
	 * 迭代求和
	 */
	public static double getSequenceSumByInterator(int n) {
		long startTime = System.currentTimeMillis();
		if(n == 1) {
			return 1d;
		}
		double sum = 1d;
		double a = 1d;
		long beforeSeqValue = 1;
		long nextSeqValue = 0;
		for(int i = 2; i <= n; i++  ) {
			//迭代关系(an = n * a(n-1) an-1 = an;)
			nextSeqValue = i * beforeSeqValue;//相当于数学中的递推公式
			beforeSeqValue = nextSeqValue;
			sum += a / nextSeqValue;
		}
		/*while(n > 1) {
			nextSeqValue = n * beforeSeqValue;
			beforeSeqValue = nextSeqValue;
			n--;
		}*/
		System.out.println("迭代求和耗时：" + (System.currentTimeMillis() - startTime) + "ms");//0ms
		return sum;
	}
}

 总结：递归效率相对较低，优先使用迭代，无法使用迭代，则使用递归