递归java堆栈溢出错误

我需要找出数组之间最长的方式（从大到小）。我试过编写recursive函数，得到了java.lang.StackOverflowError，但由于缺乏知识，我不明白为什么会发生这种情况。递归java堆栈溢出错误

首先，我初始化数组，并用随机数字填充：

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); 
    }

来源

2016-08-23 Igor Skryl

'开始++'返回start'的'原始值，并增加了1到'start' ** **之后。在++返回值之前，'++ start'在'start' **中加1。 –

你应该添加一个Log.i（“Start”，start.toString（））;到你的查找方法作为第一行，所以你看看会发生什么。 – Squirrelkiller

您需要保留当前的最大查找次数和当前值。所以改变如下：

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; 
}

，并调用它as

find(route);

来源

2016-08-23 10:34:17

非常感谢您的帮助！ –

请注意，此代码只是一个起点。例如，您需要处理空路由数组，空路由数组。 –

所有变化

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]为假。

来源

2016-08-23 10:31:50 Eran

他也应该在那里返回'find'。 – SomeJavaGuy

@KevinEsche好点 – Eran

@Eran非常感谢你的解释！ –

当您调用start ++时，执行后增量。这意味着在将参数传递给方法之后，操作发生在之后 - 这意味着您的方法只是在第一个参数上继续绕圈，直到内存用完。将其替换为start + 1，您将得到全新的一组例外以获得乐趣;）

来源

2016-08-23 10:38:54

其他用户在这里指出的算法有几个问题。但主要的问题是这个算法不能是递归的。递归地，您只能找到从零索引处开始的降序序列的长度。

正确的算法必须通过整个阵列运行：

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; 
}

来源

2016-08-23 10:46:42

非常感谢您的帮助！ –

递归java堆栈溢出错误

回答

相关问题