java - 递归java的堆栈溢出错误

Question

我需要找到数组中数字之间的最长路径(从大到小)。我尝试编写 recursive 函数并得到 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);
    }

Answer 1

首先改变

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。