0

我正在尝试解决一个需要递归回溯的问题，而我的解决方案会产生 stackoverflow 错误。我了解此错误通常表示终止条件不好，但我的终止条件似乎正确。除了可能导致 stackoverflow 错误的不良终止条件之外，还有什么其他的吗？我怎样才能找出问题所在？

编辑：抱歉试图发布代码，但它太丑陋了..

4

6 回答 6

6

正如@irreputable 所说，即使您的代码具有正确的终止条件，也可能是问题对于堆栈来说太大了（因此堆栈在达到条件之前就已用尽）。还有第三种可能：你的递归进入了循环。例如，在通过图进行深度优先搜索时，如果您忘记将节点标记为已访问，您最终会陷入循环，重新访问您已经看到的节点。

您如何确定您处于这三种情况中的哪一种？尝试找到一种方法来描述每个递归调用的“位置”（这通常会涉及函数参数）。例如，如果您正在编写一个图算法，其中一个函数在相邻节点上调用自身，那么节点名称或节点索引是递归函数所在位置的一个很好的描述。在递归函数的顶部，您可以打印描述，然后您将看到该函数做了什么，也许您可​​以判断它是否正确，或者它是否在循环。您还可以将描述存储在 HashMap 中，以检测您是否进入了一个圆圈。

于 2011-06-07T22:41:53.843 回答
3

您总是可以使用一个使用堆栈的循环，而不是使用递归。例如代替（伪代码）：

function sum(n){
  if n == 0, return 0
  return n + sum(n-1)
}

利用：

function sum(n){
  Stack stack
  while(n > 0){
    stack.push(n)
    n--
  }
  localSum = 0
  while(stack not empty){
    localSum += stack.pop()
  }
  return localSum
}

简而言之，通过将状态保存在本地堆栈中来模拟递归。

于 2011-06-07T23:04:51.590 回答
1

如果您的问题太大而无法在默认堆栈限制大小中修复，您可以使用 -Xss 选项为堆栈提供更多内存。

于 2011-06-07T22:44:19.950 回答
1

正如其他人已经提到的那样，可能有几个原因：

  • 您的代码本质上或递归逻辑存在问题。它必须是任何递归函数的停止条件、基本情况或终止点。

  • 您的内存太小，无法将递归调用的数量保留在堆栈中。大斐波那契数可能是一个很好的例子。仅供参考，斐波那契如下（有时从零开始）：

    1,1,2,3,5,8,13,...

    Fn = Fn-1 + Fn-2

    F0 = 1, F1 = 1, n>=2

于 2015-02-05T23:45:49.550 回答
0

有两个常见的编码错误可能导致您的程序进入无限循环（并因此导致堆栈溢出）：

  • 不良终止条件
  • 错误的递归调用

例子：

public static int factorial( int n ){
    if( n < n ) // Bad termination condition
        return 1;
    else
        return n*factorial(n+1); // Bad recursion call
}

否则，您的程序可能只是运行正常而堆栈太小。

于 2011-06-07T23:20:44.220 回答
0

如果您的代码是正确的，那么堆栈对于您的问题来说太小了。我们没有真正的图灵机。

于 2011-06-07T22:36:47.513 回答