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 参数。该代码完美运行，但我不知道如何运行。

当我尝试跟踪 paths[0] 计算的内容时，它总是返回 null，因为 y 将始终保持递增，直到它超出范围，此时它返回 null。 paths[1][2]和[3]也是如此，它们都返回null，不是吗？那么这个功能到底是如何工作的呢？

Answer 1

首先尝试一个非常小的例子 - 一个没有阻塞单元的 1x1 网格。正如预期的那样，没有采取任何行动。 x == tX 和 y == tY 因此您返回空字符串。到目前为止还不错。

现在看一个 2x2 网格，您位于西北角，目的地是东北角。

| @ | ^ |
| 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 code> 但关键的是 paths[2] 是 "N"。因此结果将为2，并且您将向之前的调用返回"EN"。

现在您将返回到 shortestPath 的第一次调用，这完成了我们所做的第一个选择 - 从起始位置向南。但我们还有1个选择——向东走。所以你顺着那棵树出来，它就是""。

然后是最后一步，您可以看到哪个字符串较小，并发现 "" 当然小于 "EN"。因此 result 为 2，因此您在字符串中添加 "E" 前缀，"E" 就是您的最终答案。

现在用它来找出更大的例子。它有助于绘制决策树和每个节点的棋盘状态。当到达叶子时，绘制返回代表返回值的父节点的箭头。这将有很大帮助。

Answer 2

尝试猜测您在想什么 -

您可能会想象 4 个执行路径：

路径 0:最短路径(x, y+1, tX, tY, 阻塞) -> ShortestPath(x, y+1, tX, tY, 阻塞) ->...

路径 1: ShortestPath(x, y-1, tX, tY, 阻塞) -> ShortestPath(x, y-1, tX, tY, 阻塞) ->...

路径 2: ShortestPath(x+1, y, tX, tY, 阻塞) -> ShortestPath(x+1, y, tX, tY, 阻塞) ->...

路径 3: ShortestPath(x-1, y, tX, tY, 阻塞) -> ShortestPath(x-1, y, tX, tY, Blocked) ->...

实际上，执行路径构成一棵树。每次对 ShortestPath 的调用都会再产生 4 次对 ShortestPath 的调用，即“path0”调用、“path1”调用、“path2”调用和“path3”调用。

因此，您将得到一个执行路径：path0、path0、path0...，该路径将返回 null。

但是，大多数路径将是不同调用的组合。

当递归返回到第一个shortestPath调用时，paths[0]将包含第一个移动为shortestPath（x，y+1，tX，tY，blocked）的最短路径，path[1]将包含第一个移动为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);

然后比较递归函数找到的每条路线，以找到可用的最短路径/方向串。

如果每个字符串都为 null，则 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

RECURSION：（

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

由于 paths[2] 具有最短的字符串，因此结果是 'E'+'N'。这是正确的。

由于 y = y+1 总是首先被调用，所以递归会一直运行直到超出边界。然后它将测试最后一个位置周围的其他位置，依此类推。