Go语言视频零基础入门到精通

javalearner

1. /**  
   
2. * java version "1.6.0_17"
3.   
   
4. * 尾递归与迭代实现具有相当的性能;
5.   
   
6. * 缓存实现的性能略高于非尾递归实现;
7.   
   
8. * 递归：recursive  尾递归：tail recursive;
9.   
   
10. * 尾递归时不需保存方法调用栈的参数及返回结果;于是申请的栈帧会被及时回收  
    
11. */  
    
12. public class TestFibo {   
    
13.   //斐波那契数列是从第0项和第1项开始，之后的项等于其前面相邻两项之和。
    
14.   //0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,......
    
15.     public static void main(String[] args) {   
    
16.         System.out.println(fibo3(11));
    
17.         int N=10;   
    
18.         long begin=System.currentTimeMillis();         
    
19.         System.out.println(fibo1(N)); //fibo1   
    
20.         System.out.println(System.currentTimeMillis()-begin);   
    
21.            
    
22.         begin=System.currentTimeMillis();   
    
23.         System.out.println(fibo2(N)); //fibo2   
    
24.         System.out.println(System.currentTimeMillis()-begin);   
    
25.            
    
26.         begin=System.currentTimeMillis();   
    
27.         System.out.println(fibo3(N)); //fibo3   
    
28.         System.out.println(System.currentTimeMillis()-begin);   
    
29.            
    
30.         begin=System.currentTimeMillis();   
    
31.         System.out.println(fibo4(N)); //fibo4   
    
32.         System.out.println(System.currentTimeMillis()-begin);   
    
33.     }   
    
34.     //1.1 非尾递归实现(书本上经常出现)   
    
35.     public static long fibo1(long n){   
    
36.         if(n<2) return n;   
    
37.         return fibo1(n-1)+fibo1(n-2); //小心栈溢出   
    
38.     }  
    
39. 
    
40.     //1.2 缓存实现(JS good part里有过介绍)   
    
41.     public static int LENGTH=30; //过大了就会占用过多空间   
    
42.     public static long[] cache=new long[LENGTH];   
    
43.     public static long fibo2(int n){   
    
44.         if(n<2) return n;   
    
45.         if(n>=LENGTH){   
    
46.             return fibo4(n-1)+fibo4(n-2);   
    
47.         }else if(cache[n]==0){   
    
48.             cache[n]=fibo4(n-1)+fibo4(n-2); //减少重复计算               
    
49.         }   
    
50.         return cache[n];   
    
51.     }   
    
52.     //1.3 迭代实现   
    
53.     public static long fibo3(long n){   
    
54.         if(n<2) return n;   
    
55.         long pre=1,prepre=1,ret=1;   
    
56.         for(int i=2;i< n;i++){   
    
57.             ret=pre+prepre;   
    
58.             prepre=pre;   
    
59.             pre=ret;   
    
60.         }   
    
61.         return ret;   
    
62.     }   
    
63.     //1.4 尾递归实现   
    
64.     public static long fibo4(int n){   
    
65.         if(n< 2) return n;   
    
66.         return fibo2Helper(n, 1, 1, 3); //保持与非尾递归接口不变，是借助帮助方法实现尾递归的   
    
67.     }   
    
68.     private static long fibo2Helper(int n,long prepre,long pre,int begin){   
    
69.         if(n==begin) return pre+prepre;   
    
70.         return fibo2Helper(n, pre, prepre+pre, ++begin);    //这里相当于迭代实现for-loop的浓缩     
    
71.     }   
    
72.       
    
73.     //----------------------尾递归的其他实现-------------------------------------->   
    
74.     //2. 求最大公约数   
    
75.     public static int gcd(int big,int small){   
    
76.         if(big%small==0) return small;   
    
77.         return gcd(small, big%small);   
    
78.     }   
    
79.     //3.1 阶乘--非尾递归   
    
80.     public static int fn1(int n){   
    
81.         if(n< 2) return 1;   
    
82.         return n*fn1(n-1);   
    
83.     }   
    
84.     //3.2 阶乘--尾递归   
    
85.     public static int fn2(int n){   
    
86.         if(n< 2) return 1;   
    
87.         return fn2Helper(1, n);   
    
88.     }   
    
89.     private static int fn2Helper(int ret, int n){   
    
90.         if(n< 2) return ret;   
    
91.         return fn2Helper(ret*n,n-1);   
    
92.     }   
    
93.         //4.1 翻转字符串--非尾递归   
    
94.        public static String reverse1(String s, int length){   
    
95.             if(length==0) return ""; //下一行的"+"可借助高版本JDK编译器的优化   
    
96.             return s.charAt(length-1)+reverse1(s,length-1);   
    
97.         }   
    
98.        //4.2 翻转字符串--尾递归   
    
99.        public static String reverse2(String s){   
    
100.            return reverse2Helper(s, "", s.length());   
     
101.        }   
     
102.        private static String reverse2Helper(String s,String init,int len){   
     
103.            if(len==0) return init;   
     
104.            return reverse2Helper(s, init+s.charAt(len-1), len-1);   
     
105.        }   
     
106.     //5. 验证字符串是否是回文 testHuiwen("abcdcba")   
     
107.      public static boolean testHuiwen(String s){   
     
108.          return testHuiwenHelper(s, 0, s.length());   
     
109.      }   
     
110.      private static boolean testHuiwenHelper(String s,int begin, int len){   
     
111.          if(begin< len>>1 && s.charAt(begin)==s.charAt(len-begin-1))   
     
112.              return testHuiwenHelper(s, begin+1, len);   
     
113.          else if(begin==len>>1) return true;   
     
114.          else return false;   
     
115.      }   
     
116.     //6. 翻转整数 如:1024=>4201   
     
117.      public static int reverseInt(int i){   
     
118.          return reverseIntHelper(i, 0);   
     
119.      }   
     
120.      private static int reverseIntHelper(int i, int init){   
     
121.          if(i==0) return init;   
     
122.          return reverseIntHelper(i/10, init*10+i%10);   
     
123.      }   
     
124. }  
     

复制代码

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/28/000603093.zip