Java中的高级递归(Advanced Recursion in Java)

Java中的高级递归(Advanced Recursion in Java)

我无法得到递归的结果，尤其是对于复杂的例子。 如果有人需要一些时间来解释它，我会非常感激。 我从字面上有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，不是吗？ 那么，这个功能是如何工作的？

I just can't get the hang of recursion, especially with complicated examples. I would really appreciate it if someone would take some time to explain it. I literally have 4 pieces of paper all filled with me tracing this function, but I have no idea how to put it together.

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

So what this code does is, given an x and y parameter, it tells you the shortest combination of moves you would have to make (NSWE for north, south, west, east) in order to reach the tX and tY parameters. The code works perfectly, but I have no idea how.

When I try to trace what paths[0] computes, it always comes out to null, because y will always keep incrementing until it goes out of bounds, in which it returns null. This is the same case for paths[1] [2] and [3], they all return to null, don't they? So then how the heck is this function working?

最满意答案

首先尝试一个细小的例子 - 一个没有阻塞单元格的1x1网格。 如预期的那样，没有动作要做。 x == tX和y == tY所以你返回空字符串。 目前很好。

现在看一下你在NW角落的2x2网格，目的地是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 |

现在我们来包装调用堆栈：

因为paths[1]是空字符串，其他3是null ， result是1（我假设这是你的字符串函数的工作原理）。 所以你把"N"返回到前面的呼叫。 前面的调用将显示paths[0] == null ， paths[1] == null ， paths[3] == null但临界paths[2]是"N" 。 因此result将为2，并且您将返回"EN"到先前的呼叫。

从现在开始，您将回到shortestPath的第一次调用，这包含了我们所做的第一个选择 - 从开始位置向南。 但我们还有另外1个选择 - 往东走。 所以你跟随那棵树，它简直就是"" 。

然后进入最后一步，在那里你看到哪个字符串较小，并且""当然小于"EN" 。 所以result是2，所以你在字符串前加上"E" ，而"E"是你的最终答案。

现在用它来找出更大的例子。 它有助于绘制决策树和每个节点的电路板状态。 而当你到达叶子时，绘制箭头返回到表示返回值的父节点。 这将非常有帮助。

First try it with a trivially small example - a 1x1 grid with no blocked cells. As expected, there are no moves to be made. x == tX and y == tY so you return empty string. Good so far.

Now look at a 2x2 grid where you are in the NW corner and the destination is NE.

| @ | ^ | | o | o |

When you try to go east and set paths[0] it invokes shortestPath, blocking off your current cell and setting your new location to the one below you. Now you have

| X | ^ | | @ | o |

In that invocation, it's going to try to go N, W, S and E. Ignore for simplicity that going east happens before west, so we can finish up the other 3 directions right away - they all invoke again shortestPath on an invalid location (2 out of bounds, 1 you've been to) and return null immediately. You are left going east with a new grid and location like this:

| X | ^ | | X | @ |

Again, 3 of the directions return null. Only north will give you the end result you want. When you try to go there, you once again invoke shortestPath which immediately returns empty string because the board now looks like this:

| X | @^ | | X | X |

Now we get to wrap up the call stack:

Because paths[1] was empty string and the other 3 were null, result is 1 (I assume that's how your string function works). So you return "N" to the previous call. The previous call is going to show that paths[0] == null, paths[1] == null, paths[3] == null but critically paths[2] is "N". Therefore result will be 2, and you will return "EN" to the earlier call.

Since now you are returning to the very first invocation of shortestPath, that wraps up the first choice we made - going south from the start position. But we also had 1 more choice - go east. So you follow that tree out and it is simply "".

Then comes the final step, where you see which string is smaller and get that "" is of course smaller than "EN". So result is 2, and therefore you prefix the string with "E", and "E" is your final answer.

Now use that to figure out the larger examples. It helps to draw a decision tree and the state of the board at each node. And as you get to the leaves, draw arrows going back up to the parent node representing return values. That will help immensely.