Java中的fibonacci函数的尾调用优化

前端之家收集整理的这篇文章主要介绍了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时不能完成.程序看起来像挂了.任何想法,为什么会发生这种情况?
与Head递归相比,尾递归方法花费的时间要少得多.有时比迭代方法花费更少的时间.这是否意味着java在内部执行一些尾部调用优化?
如果是这样,为什么我会在n>下给StackOverflowError 5000?

系统规格:

英特尔核心5处理器,

Windows XP,

32位Java 1.6

JVM的默认堆栈大小.

解决方法

Does it mean that java does some Tail call optimization internally?

不,不是的. HotSpot JIT编译器不实现尾部调用优化.

您正在观察的结果是您在Java基准测试中看到的不考虑JVM预热的异常的典型值.例如,调用一个方法的“前几个”时间,它将由解释器执行.然后JIT编译器将编译方法…它将获得更快的速度.

要获得有意义的结果,围绕整个周期循环运行,直到时间稳定.然后丢弃早期迭代的结果.

… why I did it give StackOverflowError at n > 5000?

这只是证明没有任何尾巴优化发生.

原文链接:https://www.f2er.com/java/124006.html

猜你在找的Java相关文章