Java中的fibonacci函数的尾调用优化
我正在研究尾部调用递归,并且发现了一些提到的文档. Sun
Java不执行尾调用优化.
我写了以下代码,以3种不同的方式计算纤维连接数: 迭代的 头递归 尾递归 public class Fibonacci { public static void main(String[] args) throws InterruptedException { int n = Integer.parseInt(args[0]); System.out.println("n Value of n : " + n); System.out.println("n Using Iteration : "); long l1 = System.nanoTime(); fibonacciIterative(n); long l2 = System.nanoTime(); System.out.println("iterative time = " + (l2 - l1)); System.out.println(fibonacciIterative(n)); System.out.println("n Using Tail recursion : "); long l3 = System.nanoTime(); fibonacciTail(n); long l4 = System.nanoTime(); System.out.println("Tail recursive time = " + (l4 - l3)); System.out.println(fibonacciTail(n)); System.out.println("n Using Recursion : "); long l5 = System.nanoTime(); fibonacciRecursive(n); long l6 = System.nanoTime(); System.out.println("Head recursive time = " + (l6 - l5)); } private static long fibonacciRecursive(int num) { if (num == 0) { return 0L; } if (num == 1) { return 1L; } return fibonacciRecursive(num - 1) + fibonacciRecursive(num - 2); } private static long fibonacciIterative(int n) throws InterruptedException { long[] arr = new long[n + 1]; arr[0] = 0; arr[1] = 1; for (int i = 2; i <= n; i++) { // Thread.sleep(1); arr[i] = arr[i - 1] + arr[i - 2]; } return arr[n]; } private static long fibonacciTail(int n) { if (n == 0) return 0; return fibHelper(n,1,1); } private static long fibHelper(int n,int m,long fibM_minus_one,long fibM) { if (n == m) return fibM; return fibHelper(n,m + 1,fibM,fibM_minus_one + fibM); } } 在运行这个程序时,我提出了一些结果: >头部递归方法在n> 50时不能完成.程序看起来像挂了.任何想法,为什么会发生这种情况? 系统规格: 英特尔核心5处理器, Windows XP, 32位Java 1.6 JVM的默认堆栈大小. 解决方法
不,不是的. HotSpot JIT编译器不实现尾部调用优化. 您正在观察的结果是您在Java基准测试中看到的不考虑JVM预热的异常的典型值.例如,调用一个方法的“前几个”时间,它将由解释器执行.然后JIT编译器将编译方法…它将获得更快的速度. 要获得有意义的结果,围绕整个周期循环运行,直到时间稳定.然后丢弃早期迭代的结果.
这只是证明没有任何尾巴优化发生. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |