Java中的高級遞歸

Question

我只是無法得到遞歸的竅門，尤其是對於複雜的示例。如果有人需要一些時間來解釋它，我會非常感激。我從字面上有4張紙滿了我追蹤這個功能，但我不知道如何把它放在一起。

public static String shortestPath(int x, int y, int tX, int tY,boolean blocked[][]) { 

     if(x>blocked.length-1 || y>blocked[0].length-1 || x<0 || y<0) 
      return null; 
     if(blocked[x][y]==true) 
      return null; 
     if(x==tX && y==tY) 
      return ""; 

     String paths[]=new String[4]; 
     blocked[x][y]=true; //this just means this coordinate is blocked, so dont use it 
     paths[0]=shortestPath(x, y+1, tX, tY, blocked); 
     paths[1]=shortestPath(x, y-1, tX, tY, blocked); 
     paths[2]=shortestPath(x+1, y, tX, tY, blocked); 
     paths[3]=shortestPath(x-1, y, tX, tY, blocked); 
     blocked[x][y] = false; 
     int result=findShortestString(paths, 0, 3); 
//findShortestString just takes an array of strings, 
//with 0 being the lo index and 3 being the hi, 
//and returns the index that contains the string with the shortest length. 
     //5 
     if(paths[result]==null) 
      return null; 
     else{ 

      if(result==0) 
       return 'N' + paths[result]; 
      if(result==1) 
       return 'S' + paths[result]; 
      if(result==2) 
       return 'E' + paths[result]; 
      if(result==3) 
       return 'W' + paths[result];} 

     return paths[result]; 

所以這段代碼所做的是什麼，給定一個X和Y參數，它告訴你的移動最短的組合，你將不得不作出（NSWE爲北，南，西，東），以達到tX和tY參數。代碼完美地工作，但我不知道如何。

當我嘗試追蹤路徑[0]計算的路徑時，它總是會出現爲空，因爲y總是會一直增加，直到超出邊界，並返回空值。路徑[1] [2]和[3]的情況也是如此，它們都返回null，不是嗎？那麼，這個功能是如何工作的？

Answer 1

首先用一個普通的小例子 - 一個沒有阻塞單元的1x1網格來嘗試它。如預期的那樣，沒有動作要做。 x == tX和y == tY所以你返回空字符串。目前很好。

現在看一下2x2網格，你在NW的角落，目的地是NE。

| @ |^| 
| o | o | 

當您嘗試往東走，並設置paths[0]它調用shortestPath，堵住你的當前單元格並設置新的位置下面你的人。現在你有

| X |^| 
| @ | o | 

在該調用，它會嘗試去N，W，S和E忽略了簡單西部之前去東部發生的，所以我們可以在其他3個方向完事馬上 - 他們都會在無效位置再次調用shortestPath（2次出界，1次出場），並立即返回null。你留下了一個新的網格和位置這樣去東：

| X |^| 
| X | @ | 

再次，方向3回null。只有北方會給你想要的最終結果。當你試圖去那裏，你再次調用shortestPath其立即返回空字符串，因爲該板目前看起來是這樣的：

| X | @^ | 
| X | X | 

現在，我們得到的收官調用堆棧：

1. 因爲paths[1]是空字符串，其他3個是null，result是1（我假設你的字符串函數是如何工作的）。因此，您將"N"返回到先前的呼叫。
2. 上一個電話會顯示paths[0] == null,paths[1] == null,paths[3] == null但嚴重paths[2]是"N"。因此result將爲2，並且您將返回"EN"以前的呼叫。

從現在開始，您將返回第一次調用shortestPath，這包含了我們做出的第一個選擇 - 從開始位置向南行進。但我們還有另外1個選擇 - 往東走。所以你跟隨那棵樹，它只是""。

接下來是最後一步，您會看到哪個字符串較小，並且""當然小於"EN"。因此result是2，因此您在字符串前加上"E"，而"E"是您的最終答案。

現在用它來找出更大的例子。它有助於繪製決策樹和每個節點的電路板狀態。而當你到達葉子時，繪製箭頭返回到表示返回值的父節點。這將非常有幫助。

Answer 2

試圖猜測你在想什麼 -

你可能會想象4條的執行路徑：

路徑0：最短路徑（X，Y + 1，TX，TY，阻塞） - >最短路徑（ （x，y-1，tX，tY，blocking） - > shortestPath（x，y-1，tX， （x + 1，y，tX，tY，blocked） - > ...

path 2：shortestPath 。

路徑3：最短路徑（X-1，Y，TX，TY，阻止） - >最短路徑（X-1，Y，TX，TY，阻止） - > ...

在現實中，執行路徑構成一棵樹。每個對shortestPath的調用都會產生另外4個對shortestPath，「path0」調用，「path1」調用，「path2」調用和「path3」調用的調用。

所以，你會得到一個path0，path0，path0 ......這將返回null的執行路徑。

但是，大多數路徑將是不同調用的組合。

當遞歸返回到第一個shortestPath調用時，paths [0]將包含其FIRST移動爲shortestPath（x，y + 1，tX，tY，blocking）的最短路徑，path [1] FIRST是shortestPath（x，y-1，tX，tY，被封鎖）等。

Answer 3

這並不複雜。

該部分檢查，如果x或y參數是有效的（無論是在邊界或不阻塞）

if(x>blocked.length-1 || y>blocked[0].length-1 || x<0 || y<0) 
    return null; 
if(blocked[x][y]==true) 
    return null; 

這裏，如果位置在到達目的地現在

if(x==tX && y==tY) 
    return ""; 

到檢查遞歸部分，該函數遞歸爲四個其他函數，每個函數相對於當前位置可用的NSWE方向：

String paths[]=new String[4]; 
blocked[x][y]=true; //this just means this coordinate is blocked, so dont use it 
paths[0]=shortestPath(x, y+1, tX, tY, blocked); 
paths[1]=shortestPath(x, y-1, tX, tY, blocked); 
paths[2]=shortestPath(x+1, y, tX, tY, blocked); 
paths[3]=shortestPath(x-1, y, tX, tY, blocked); 
blocked[x][y] = false; 
int result=findShortestString(paths, 0, 3); 

然後比較遞歸函數找到的每條路徑，以找到可用的最短路徑/一串方向。

如果每個字符串都爲空，findShortestString（）可能返回null，因此無法從該遞歸的起始位置到達目的地。

遞歸的當前位置被標記爲阻塞，因此算法不會返回到之前訪問的位置。

if(paths[result]==null) 
    return null; 

這會檢查findShortestString是否未找到任何有效路徑。

最後，在遞歸中找到的相對於當前位置的路徑被添加到找到最短路徑的遞歸調用的方向。

示例： 假設地圖只有一條到達目的地的有效路徑，所有其他位置都被鎖定。起始位置是[0] [0]和目的地爲[1] [1]（X + 1 = N，Y + 1 = E） MAP：

(y-line increases upwards, x-column increases rightwards) 
0D 
SX 

S-start 
X-blocked 
0-not blocked 
D-destination 

第一次調用：

-x,y are within boundaries and are not the destination 
-blocks current positions([0][0]) 
-calls function for y = y+1 -> is blocked (returns NULL) 
-calls function for y = y-1 -> out of boundaries (returns NULL) 
-calls function for x = x+1 -> path is ok 

遞推：

-blocks current position[1][0] 
-calls function for y = y+1 -> Destination!(returns "") 
-calls function for y = y-1 -> out of boundaries(returns NULL) 
-calls function for x = x+1 -> out of boundaries(returns NULL) 
-calls function for x = x-1 -> blocked(returns NULL) (this would be the starting position) 
Since paths[0] has the shortest string("") and the result is 'N'+"" 

（回第一迭代）

-calls function for x = x-1 -> out of boundaries(returns NULL) 

由於路徑[2]具有最短的字符串，因此結果爲'E'+'N'。哪個是對的。

由於y = y + 1總是先調用，遞歸運行直至超出邊界。然後它將測試最後位置周圍的其他位置等等。