java - 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 参数，它会告诉您为了达到 tX 和 tY 参数必须进行的最短移动组合(NSWE 表示北、南、西、东) .该代码完美运行，但我不知道如何运行。

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

Answer 1

首先尝试使用一个非常小的示例 - 一个没有阻塞单元格的 1x1 网格。不出所料，没有任何 Action 可做。 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" 就是您的最终答案。

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