fibonacci的几种实现及尾递归

/**
 * java version "1.6.0_17"<br>
 * 尾递归与迭代实现具有相当的性能;<br>
 * 缓存实现的性能略高于非尾递归实现;<br>
 * 递归：recursive  尾递归：tail recursive;<br>
 * 尾递归时不需保存方法调用栈的参数及返回结果;于是申请的栈帧会被及时回收
 */
public class TestFibo {

	public static void main(String[] args) {
		int N=50;
		long begin=System.currentTimeMillis();		
		System.out.println(fibo1(N)); //fibo1
		System.out.println(System.currentTimeMillis()-begin);
		
		begin=System.currentTimeMillis();
		System.out.println(fibo2(N)); //fibo2
		System.out.println(System.currentTimeMillis()-begin);
		
		begin=System.currentTimeMillis();
		System.out.println(fibo3(N)); //fibo3
		System.out.println(System.currentTimeMillis()-begin);
		
		begin=System.currentTimeMillis();
		System.out.println(fibo4(N)); //fibo4
		System.out.println(System.currentTimeMillis()-begin);
	}
//1.1 非尾递归实现(书本上经常出现)  
public static long fibo1(long n){  
	if(n<2) return n;  
	return fibo1(n-1)+fibo1(n-2); //小心栈溢出  
}  
//1.2 缓存实现(JS good part里有过介绍)  
public static int LENGTH=30; //过大了就会占用过多空间  
public static long[] cache=new long[LENGTH];  
public static long fibo2(int n){  
	if(n<2) return n;  
	if(n>=LENGTH){  
		return fibo2(n-1)+fibo2(n-2);  
	}else if(cache[n]==0){  
		cache[n]=fibo2(n-1)+fibo2(n-2); //减少重复计算              
	}  
	return cache[n];  
}  
//1.3 迭代实现  
public static long fibo3(long n){  
	if(n<2) return n;  
	long pre=1,prepre=1,ret=0;  
	for(int i=2;i<n;i++){  
		ret=pre+prepre;  
		prepre=pre;  
		pre=ret;  
	}  
	return ret;  
}  
//1.4 尾递归实现  
public static long fibo4(int n){  
	if(n<2) return n;  
	return fibo4Helper(n, 1, 1, 3); //保持与非尾递归接口不变，是借助帮助方法实现尾递归的  
}  
private static long fibo4Helper(int n,long prepre,long pre,int begin){  
	if(n==begin) return pre+prepre;  
	return fibo4Helper(n, pre, prepre+pre, ++begin);    //这里相当于迭代实现for-loop的浓缩    
} 
	
	//----------------------尾递归的其他实现-------------------------------------->
	//2. 求最大公约数
	public static int gcd(int big,int small){
		if(big%small==0) return small;
		return gcd(small, big%small);
	}
	//3.1 阶乘--非尾递归
	public static int fn1(int n){
		if(n<2) return 1;
		return n*fn1(n-1);
	}
	//3.2 阶乘--尾递归
	public static int fn2(int n){
		if(n<2) return 1;
		return fn2Helper(1, n);
	}
	private static int fn2Helper(int ret, int n){
		if(n<2) return ret;
		return fn2Helper(ret*n,n-1);
	}
        //4.1 翻转字符串--非尾递归
	   public static String reverse1(String s, int length){
			if(length==0) return ""; //下一行的"+"可借助高版本JDK编译器的优化
			return s.charAt(length-1)+reverse1(s,length-1);
		}
	   //4.2 翻转字符串--尾递归
	   public static String reverse2(String s){
		   return reverse2Helper(s, "", s.length());
	   }
	   private static String reverse2Helper(String s,String init,int len){
		   if(len==0) return init;
		   return reverse2Helper(s, init+s.charAt(len-1), len-1);
	   }
    //5. 验证字符串是否是回文 testHuiwen("abcdcba")
	 public static boolean testHuiwen(String s){
		 return testHuiwenHelper(s, 0, s.length());
	 }
     private static boolean testHuiwenHelper(String s,int begin, int len){
    	 if(begin< len>>1 && s.charAt(begin)==s.charAt(len-begin-1)) 
    		 return testHuiwenHelper(s, begin+1, len);
    	 else if(begin==len>>1) return true;
    	 else return false;
     }
    //6. 翻转整数 如:1024=>4201
	 public static int reverseInt(int i){
		 return reverseIntHelper(i, 0);
	 }
	 private static int reverseIntHelper(int i, int init){
		 if(i==0) return init;
		 return reverseIntHelper(i/10, init*10+i%10);
	 }
}

最后show一下强大的scala，用一行代码获取斐波那契数列的前30位：

>(1 to 28).foldLeft("0,1")((a,b)=>a+","+a.split(",").takeRight(2).map(_.toInt).reduceLeft(_+_))  

>0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229  

>(1 to 28).foldLeft(List(1,0))((a,b)=>(a.head+a.tail.head)::a).reverse.mkString(",")  

>0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229


scala> def fibo(n:Int)=(1 to n).foldLeft(List(0,1))((a,b)=>a:+(a.init.last+a.last))
fibo: (n: Int)List[Int]

scala> fibo(10)
res4: List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89)

材料备注：http://hi.baidu.com/donghongchen/blog/item/989089f1409caea3a50f5254.html