遞歸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堆棧溢出錯誤

回答

相關問題