递归  尾递归

尾递归2个特点
1.在尾部调用的是函数自身（Self-called）
2.可通过优化，使得计算仅占常量栈空间（Stack Space）
       
       

斐波那契数列（Fibonacci sequence）
又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”


计算第45项
递归版本   耗时 6770 MS
尾递归版本 耗时 0 MS

result=1134903170,time1=6770
result=1134903170,time2=0


public class Fibonacci {

	public static void main(String[] args) {
		int n = 45;
		long start = System.currentTimeMillis();
		long result = fibonacci(n);
		long end = System.currentTimeMillis();
		long time = end - start;

		System.err.println("result=" + result + ",time1=" + time);

		start = System.currentTimeMillis();
		result = advanced(n, 0L, 1L);
		end = System.currentTimeMillis();
		time = end - start;

		System.err.println("result=" + result + ",time2=" + time);
	}

	// 递归版本
	private static long fibonacci(int n) {
		if (n < 0)
			return -1;
		if (n <= 1)
			return n;
		return fibonacci(n - 1) + fibonacci(n - 2);
	}

	// 尾递归版本
	private static long advanced(int n, long ret1, long ret2) {
		if (n < 0) {
			return -1;
		}
		if (n == 0) {
			return ret1;
		}
		if (n == 1) {
			return ret2;
		}
		return advanced(n - 1, ret2, ret1 + ret2);
	}

}