logo标签列表

Java递归中的堆栈溢出错误

javarecursionstack-overflow
3

我需要找到数组中从大到小的最长路径。我尝试写了一个递归函数，但是因为我的知识不足，我不明白为什么会出现java.lang.StackOverflowError。

首先，我初始化了一个数组并用随机数填充它：

public long[] singleMap = new long[20];
for (int i = 0; i < 20; i++) {
        singleMap[i] = (short) random.nextInt(30);
    }

然后，我尝试查找最长的倒数数字路径（例如{ 1, 4, 6, 20, 19, 16, 10, 6, 4, 7, 6, 1 ...}），并返回这样的数字计数。

 public int find(long[] route, int start) {
    if (route[start] > route[start + 1]) {
        find(route, start++);
    } else {
        return start;
    }
    return start;
}

所以这里是日志：
 08-23 13:06:40.399 4627-4627/itea.com.testnotification I/dalvikvm:   threadid=1: stack overflow on call to    Litea/com/testnotification/MainActivity;.find:ILI
 08-23 13:06:40.399 4627-4627/itea.com.testnotification I/dalvikvm:   method requires 36+20+12=68 bytes, fp is 0x4189e318 (24 left)
 08-23 13:06:40.399 4627-4627/itea.com.testnotification I/dalvikvm:   expanding stack end (0x4189e300 to 0x4189e000)
 08-23 13:06:40.400 4627-4627/itea.com.testnotification I/dalvikvm: Shrank stack (to 0x4189e300, curFrame is 0x418a3e88)
 08-23 13:06:40.400 4627-4627/itea.com.testnotification D/AndroidRuntime: Shutting down VM
 08-23 13:06:40.400 4627-4627/itea.com.testnotification W/dalvikvm: threadid=1: thread exiting with uncaught exception (group=0x41a8ed40)
 08-23 13:06:40.414 4627-4627/itea.com.testnotification E/AndroidRuntime: FATAL EXCEPTION: main
                                                                         Process: itea.com.testnotification, PID: 4627
                                                                     java.lang.StackOverflowError
                                                                         at itea.com.testnotification.MainActivity.find(MainActivity.java:46)
                                                                         at itea.com.testnotification.MainActivity.find(MainActivity.java:46)

我很感激任何解释，因为所有相关问题都没有帮到我。如果我的功能有问题，请指出或解释。
编辑： 我忘了说，我使用“for”来检查每个“点”之间最长的路径。
  for (int i = 0; i < singleMap.length - 1; i++) {
        int x = find(singleMap, i);
        System.out.println("steps = " + x);
    }
start++ 返回 start 的原始值，并在此之后将其加1。++start 在返回值之前先将 start 加1。 - Ray O'Kalahjan
你应该在你的find方法中作为第一行添加Log.i("Start", start.toString());，这样你就可以看到发生了什么。 - Squirrelkiller
4个回答
5

首先更改

find(route, start++)

为了

find(route, start+1)

由于后置自增运算符返回变量的原始值，因此递归永远不会前进，导致StackOverflowError。您还应该添加一个停止条件，否则下一个异常将是ArrayIndexOutOfBoundsException。正如Kevin所评论的那样，您还应该对find(route, start++)返回的值做些事情。否则根本没有必要调用它。除了这些问题之外，您的逻辑是错误的。该方法将返回以数组开头开始的降序序列的最后一个索引，这告诉您有关最长降序序列的信息不足。例如，对于{1, 4, 6, 20, 19, 16, 10, 6, 4, 7, 6, 1 ...}，您的方法将返回0（数组的第一个索引），因为route [0]> route [1]为false。
3
他也应该在那里返回 find。 - SomeJavaGuy
3
您需要维护当前最大查找值和当前值。因此，更改如下：
public int find(int[] route, int start, int max, int currentMax) {
    if (currentMax > max) {
        max = currentMax;
    }
    if (start == route.length - 1) {
        return max;
    }
    if (route[start] > route[start + 1]) {
        return find(route, start + 1, max, currentMax + 1);
    }
    return find(route, start + 1, max, 1);
}

并使用一个起始标签调用它。
find(route, 0, 1, 0);

第二种选择是不使用递归重写它：
public int find(int[] route) {
    int max = 1;
    int currentMax = 1;
    for (int i = 0; i < route.length - 1; i++) {
        if (route[i] > route[i + 1]) {
            currentMax++;    // If next element is lower increment currentMax
            if (currentMax > max) {
                max = currentMax;   // If currentMax is the new max update max
            }

        } else {
            currentMax = 1;   // If next element is not lower restart from 1
        }
    }
    return max;
}

并将其称为

find(route);
请注意，此代码仅为起点。您需要处理空路由数组、null路由数组等情况。 - Davide Lorenzo MARINO
1
当你调用start++时，你执行了一个后自增的操作。这意味着操作发生在将参数传递给方法之后 - 这意味着你的方法只会在第一个参数上循环，直到内存耗尽。 将其替换为start+1，你将得到一堆新的异常来娱乐 ;)
1
你在算法中有几个问题，其他用户已经指出。但是主要问题在于这个算法不能是递归的。递归只能找到从零索引开始的下降序列的长度。
一个正确的算法必须遍历整个数组:
public static int find(long[] route) {
    int maxIdx = 0;
    int maxCount = 1;
    for (int i = 1, c = 0; i < route.length; i++) {
        if (route[i] < route[i - 1]) {
            if (++c >= maxCount) {
                maxCount = c;
                maxIdx = i - c;
            }
        } else {
            c = 0;
        }
    }
    return route.length == 0 ? -1 : maxIdx;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接