/** * java version "1.6.0_17"
* 尾遞歸與迭代實現具有相當的性能;
* 緩存實現的性能略高于非尾遞歸實現;
* 遞歸：recursive 尾遞歸：tail recursive;
* 尾遞歸時不需保存方法調用棧的參數及返回結果;于是申請的棧幀會被及時回收 */ public class TestFibo { //斐波那契數列是從第0項和第1項開始，之后的項等于其前面相鄰兩項之和。 //0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,...... public static void main(String[] args) { System.out.println(fibo3(11)); int N=10; 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 fibo4(n-1)+fibo4(n-2); }else if(cache[n]==0){ cache[n]=fibo4(n-1)+fibo4(n-2); //減少重復計算 } return cache[n]; } //1.3 迭代實現 public static long fibo3(long n){ if(n<2) return n; long pre=1,prepre=1,ret=1; 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 fibo2Helper(n, 1, 1, 3); //保持與非尾遞歸接口不變，是借助幫助方法實現尾遞歸的 } private static long fibo2Helper(int n,long prepre,long pre,int begin){ if(n==begin) return pre+prepre; return fibo2Helper(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); } }
《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的尾递归及示例（JAVA）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。