时间戳

首页 > 解决方案 > 关于递归的常见行业惯例是什么？或者我们怎么知道我们是否应该完全避免递归？

java - 关于递归的常见行业惯例是什么？或者我们怎么知道我们是否应该完全避免递归？

问题描述

我确实理解递归的问题之一是堆栈深度，它可能导致非常深的递归问题。此外，我知道递归可以用显式堆栈使用来代替，以避免此类问题。
另一方面，如果我没记错的话，递归允许代码简洁明了（我会说很漂亮），并且是在所有标准教科书中呈现算法的主要方式。

我的问题比理论更实际：

我正在运行以下程序来弄清楚在我得到一个之前我能走多远java.lang.StackOverflowError
我的理由是，例如，如果我有一个小的图形视图，有几千个顶点并且每次遍历的处理最少，那么递归与迭代方法可能无关紧要：

public static void foo(int i) {
   if (i % 5000 == 0) {
        System.out.println(i);
   }
   foo(i + 1);
}

public static void main(String[] args) {
    foo(0);
}

输出是：

Exception in thread "main" java.lang.StackOverflowError
5000
10000

因此，我的解释是，程序会在处理超过 10000 个顶点后进行 DFS，这听起来很小。
谷歌搜索我发现当我们运行一个程序时，堆栈的默认大小是可以配置的，但我想知道这个行业的惯例是什么？

是否为重型服务器程序设置显式线程堆栈大小，以便上面的示例在实践中不会成为问题？还是完全避免编写递归？还是我的例子不能真正代表一个问题？

更新
我明白上面的代码示例是一个无限递归。这样做的唯一目的是看看它在断裂之前能走多远。

标签： javaalgorithmrecursionoptimizationgraph-algorithm

解决方案

是否为重型服务器程序设置显式线程堆栈大小，以便上面的示例在实践中不会成为问题？

不。

  1. 例子是无限递归。这将永远是一个问题。
  2. Java 中没有足够大的堆栈大小。它需要无限量的堆栈空间。
  3. （在实现“尾调用优化”的语言/实现中，不会出现堆栈溢出。但 Java 不是这样的语言。）

还是完全避免编写递归？

不，递归很好……只要你能预测递归的最大深度。

还是我的例子不能真正代表一个问题？

它并没有真正的代表性。

然而，现实世界中显然存在一些问题，其中递归方法对于某些输入会失败。

谷歌搜索我发现当我们运行一个程序时，堆栈的默认大小是可以配置的，但我想知道这个行业的惯例是什么？

设置默认堆栈大小没有相关的“行业惯例”。所需的堆栈大小取决于实际算法及其实现以及输入数据。

但是，当您无法对递归深度设置合理的界限时，尝试实现递归解决方案是一个坏主意。

对于给定的 Java 程序，计算给定递归深度所需的堆栈空间在技术上是可行的，但计算将取决于平台。

JVM 对最大堆栈大小进行了限制。例如，对于 64 位模式下 x86-64 上的 Java 11，您不能设置-Xss大于1g. （这可能是件好事。）

推荐阅读