如何提高 Java 递归的速度

Question

问题：如何使用其他技术加速递归方法。

简单的斐波那契数列方法使用递归来输出输入的第 N 个数字。

任何建议都会很棒，谢谢。

前任; 输入 50 需要将近一分钟才能最终获得输出。

编辑：更改问题文本，因为它不是递归太慢，而是我的代码。

public static long cycle(int x) {
  if(x<=1) {
    return x;
  } else {
    return cycle(x-1)+cycle(x-2);
  }
}

Answer 1

让我们想想这里的根本问题。您希望您的代码在相同的硬件上执行得更快，这是一个称为优化的重要软件过程。

在优化期间，您需要分析您的应用程序以确定最慢的组件是什么，并对其进行改进。在您的情况下，我可以非常肯定地猜测，这里程序中最慢的部分是函数调用。根据我们得到的函数调用次数绘制第 n 个斐波那契项：

如您所见，增长呈指数级增长。注意：有一些数学方法可以解决这个问题，特别是如本页所述。如果您的意图是创建一个快速执行的函数，那么时间复杂度的指数增长总是要避免的（当然，有些函数必须是指数函数，但这不是其中之一）。看着cycle(50)4 * 10^10 次函数调用，你说它在近一分钟内完成，相当于每秒约6.666 亿次函数调用（或每 1.5 ns 1 次调用），基于此调用 java 慢似乎不太公平. 底线是，无论编译器的优化技术有多好或多快，它都无法修复您的时间复杂度，它只能使每个操作稍微快一点（阅读如果您想了解更多信息，请进行尾调用优化）。

您在这里遇到的主要问题是您多次重新计算相同的斐波那契数，想想您重新计算了多少次cycle(2)。这就是指数复杂度的来源，多次重新计算相同的斐波那契数，这是无用的。

解决问题的最简单方法是通过迭代，但您已经表示对迭代器不感兴趣。

下一个简单的方法是使用查找表 (LUT) 将预先计算的斐波那契数列存储在数组中以便快速访问。这种方法的问题可以很容易地显示如下：

上图显示了 n 高达 10 的 LUT 的影响。虽然我们降低了指数的幂，但我们仍在处理指数，这并不能完全解决问题（假设您需要做cycle(100)什么？）。

解决方案是使用用户 1.618 评论中提到的记忆。这意味着在计算每个 Fibonacci 项时保存它的结果，同时生成 LUT，从不重新计算任何结果两次。

下图展示了这种效果：

在cycle(50)，您将需要 97 次方法调用，以 1.5 ns/call 的速度将在 145.5 ns 内完成，比您眨眼的速度还要快（由于额外的时间查看 LUT，它可能不会那么快以及没有那么热）。

在java中实现这个，我们得到：

private static long[] fib_numbers;

public static long cycle(int x){
    if(fib_numbers == null || fib_numbers.length <= x){
        fib_numbers = new long[x + 1];
    }

    return cycle_rec(x);
}

private static long cycle_rec(int x) {
    if(x <= 1){
        return x;
    }else if(fib_numbers[x] != 0){
        // previously computed result exists, return directly

        return fib_numbers[x];
    }else{
        // compute and store cycle(x)
        fib_numbers[x] = cycle_rec(x-1)+cycle_rec(x-2);

        return fib_numbers[x];
    }
}

该数组fib_numbers包含我们每个方法调用动态生成的 LUT。cycle()在内部调用cycle_rec()（我们的递归函数）之前，我们公开了一个公共方法来设置要使用的数组。