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,北,西,东).代码完美无缺,但我不知道如何.

当我尝试跟踪哪些路径[0]计算时,它总是变为空,因为y将始终保持递增,直到它超出边界,其中它返回null.这与路径[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,它包含了我们做出的第一个选择 - 从起始位置向南移动.但我们还有一个选择 - 去东部.所以你跟着那棵树走了,简直就是这样"".

然后是最后一步,在那里你可以看到哪个字符串更小并且""当然小于"EN".所以result是2,因此你在字符串前加上"E",并且"E"是你的最终答案.

现在用它来弄清楚更大的例子.它有助于绘制决策树和每个节点的电路板状态.当你到达树叶时,绘制箭头返回到表示返回值的父节点.这将有很大帮助.