尾递归会将本次方法的结果计算出来，直接传递给下个方法。效率很快。
一般的递归，在本次方法结果还没出来的时候，就调用了下次的递归， 而程序就要将部分的结果保存在内存中，直到后面的方法结束，再返回来计算。如果递归比较大，可能会照成内存溢出。
实践证明，尾递归 ，确实比普通递归效率高。
下面的例子 ，用 普通递归需要10s完成 ， 而用尾递归，只用了1s不到
package com.zf.dg;
/**
* 题目
* 有一种母牛,出生后第三年,开始生育,每年都生一头
母牛(貌似单性生育,这里就没公牛什么事儿);生出来的小母牛也符合同样的规律,出生后第三年,开始生
育,每年都生一头母牛;该种母牛是永生的,而且永远拥有生育能力,生命不止,生育不止,生生不息。第一
年时,只有一头母牛。请问第n年时,共有母牛多少头?
规律如下： 第n年的数量 = 第n-1年牛的数量 + 第 n -2 年牛的数量
1 1
2 1
3 2
4 3
5 5
6 8
*/
public class Test2 { /**
* 普通树形递归
* @param n
* @return
*/
public static int fun(int n){
if(n < 3){
return 1 ;
}else{
return fun(n -1) + fun(n - 2);
}
} /**
* 将普通树形递归变成尾递归
* 从第 current 年一直计算 累加 到第n年
* @param last 上一年牛的数量
* @param result 当前年的牛的数量
* @param current 当前第几年
* @param n 要计算的年数
* @return
*/
public static int fun2(int last , int result , int current , int n){
if(n < 3){
return 1 ;
}else if(current == n)
return result ;
else{
return fun2(result , result + last , ++current , n );
}
} /**
* 将上面的方法包装
* 思路：从第二年开始计算 ，一直计算到第n年 ，因为第二年我们能够知道他的前上一年 牛的数量 与 当前年的数量
* @param n
* @return
*/
public static int fun3(int n ){
return fun2(1 , 1 , 2 , n);
} public static void main(String[] args) {
long start = System.currentTimeMillis();
System.out.println(fun(45));
// System.out.println(fun3(45));
long end = System.currentTimeMillis();
System.out.println("用时：" + ( end - start ) / 1000);
} }