10

我正在研究 Tail call recursion 并遇到了一些提到的文档。Sun Java 没有实现尾调用优化。我编写了以下代码以 3 种不同的方式计算斐波那契数：1. 迭代 2. 头递归 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, 0, 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);
    }
}

在运行这个程序时，我得出了一些结果：

  1. 对于 n>50，Head Recursive 方法无法完成。程序看起来像挂了。任何想法，为什么会发生这种情况？
  2. 与头递归相比，尾递归方法花费的时间要少得多。有时比迭代方法花费的时间更少。这是否意味着java在内部做了一些Tail调用优化？如果是这样，为什么我会在 n > 5000 时给出 StackOverflowError？

系统规格：

英特尔酷睿 5 处理器，

视窗XP，

32 位 Java 1.6

JVM 的默认堆栈大小。

4

4 回答 4

12

这是否意味着java在内部做了一些Tail调用优化？

不，不是的。HotSpot JIT 编译器不实现尾调用优化。

您观察到的结果是您在未考虑 JVM 预热的 Java 基准测试中看到的典型异常。例如，一个方法被调用的“前几次”，它将由解释器执行。然后 JIT 编译器将编译该方法......它会变得更快。

要获得有意义的结果，请围绕整个批次进行循环并运行多次，直到时间稳定。然后丢弃早期迭代的结果。

...为什么我在 n > 5000 时给出了 StackOverflowError？

这只是证明没有发生任何尾调用优化的证据。

于 2011-03-28T00:31:21.487 回答
3

对于第一个问题，什么是 2^50（或接近的值）？递归 Fib 函数中的每个数字 N 都会调用它两次（之前的 2 次）。这些中的每一个都调用了 2 个先前的迭代，等等。所以它增长到 2^(Nk) 的递归（k 可能是 2 或 3）。

第二个问题是因为第二个问题是直接 N 递归。它不是双头(N-1),(N-2)，而是简单地从 M=1，M=2...M=N 构建。每一步，都会保留 N-1 值以供添加。由于它是 O(N) 操作，因此它与迭代方法相当，唯一的区别是 JIT 编译器如何优化它。但是，递归的问题在于，它需要为您堆叠到框架上的每个级别占用大量内存 - 您会在某个限制下耗尽内存或堆栈空间。 它通常仍应比迭代方法慢。

于 2011-03-28T00:14:40.610 回答
2

您可以使用记忆化来避免头部递归。

我已经测试了以下代码，当 N <=40 时，这种方法很糟糕，因为 Map 进行了权衡。

private static final Map<Integer,Long> map = new HashMap<Integer,Long>();

private static long fibonacciRecursiveMemoization(int num) {
    if (num == 0) {
        return 0L;
    }
    if (num == 1) {
        return 1L;
    }

    int num1 = num - 1;
    int num2 = num - 2;

    long numResult1 = 0;
    long numResult2 = 0;

    if(map.containsKey(num1)){
        numResult1 = map.get(num1);
    }else{
        numResult1 = fibonacciRecursiveMemoization(num1);
        map.put(num1, numResult1);
    }

    if(map.containsKey(num2)){
        numResult2 = map.get(num2);
    }else{
        numResult2 = fibonacciRecursiveMemoization(num2);
        map.put(num2, numResult2);
    }

    return numResult1 + numResult2;
}

当 n 的值：44

使用迭代：迭代时间 = 6984

使用尾递归：尾递归时间 = 8940

使用记忆递归：记忆递归时间 = 1799949

使用递归：头部递归时间 = 12697568825

于 2011-12-04T00:47:07.217 回答
2

关于第 1 点：在没有记忆的情况下递归计算斐波那契数会导致运行时间在n. 这适用于任何不会自动记忆函数结果的编程语言（例如大多数主流的非函数式语言，例如 Java、C#、C++，...）。原因是相同的函数会被一遍又一遍地调用——例如f(8)会调用f(7)and f(6); f(7)将调用f(6)and f(5)，因此f(6)会被调用两次。这种效应会传播并导致函数调用数量呈指数增长。这是调用哪些函数的可视化：

f(8)
 f(7)
  f(6)
   f(5)
    f(4)
     ...
    f(3)
     ...
   f(4)
    ...
  f(5)
   f(4)
    ...
   f(3)
    ...
 f(6)
  f(5)
   ...
  f(4)
   ...
于 2011-03-28T00:15:28.140 回答