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总是先调用，递归运行直至超出边界。然后它将测试最后位置周围的其他位置等等。