java 计算迷宫中从(0，0)到(n，m)的总路径的程序

iezvtpos 于 2023-01-07 发布在 Java

关注(0)|答案(2)|浏览(111)

我是递归概念的新手。下面是计算从（0，0）到（n，m）的路径总数的代码。到达最终位置的规则是我们只能向右或向下移动。我无法理解递归是如何工作的。
我试图通过使用print语句来理解它，但无法理解在第三次调用'' rightPath ''之后发生了什么。

public class Main{
  public static int countPaths(int i, int j, int n, int m){
      if(i==n || j==m){
          return 0;
      }
      if(i==n-1 && j==m-1){
          return 1;
      }
      int downPath = countPaths(i+1, j, n, m);
      int rightPath = countPaths(i, j+1, n, m);
      return downPath + rightPath;
  }
  public static void main(String[] args){
      int n = 3, m = 3;
      int totalPaths = countPaths(0, 0, n, m);
      System.out.println(totalPaths);
  }
}

谁来解释一下递归是怎么工作的。

Java

来源：https://stackoverflow.com/questions/75022717/program-to-calculate-total-paths-in-a-maze-from-0-0-to-n-m

2条答案

按热度按时间

euoag5mw1#

不确定，但也许这可以帮助你：

countPaths(0, 0, 3, 3) // (0, 0)
    = countPaths(0 + 1, 0, 3, 3) // (1, 0)
        = countPaths(1 + 1, 0, 3, 3) // (2, 0)
        + countPaths(1, 0 + 1, 3, 3) // (1, 1)
            [...]
    + countPaths(0, 0 + 1, 3, 3) // (0, 1)
        = countPaths(0 + 1, 1, 3, 3) // (1, 1)
        + countPaths(0, 1 + 1, 3, 3) // (0, 2)
            [...]

它旨在向您展示如何嵌套执行函数以及计算和返回哪些值。

赞(0）回复(0）举报 2023-01-07

ojsjcaue2#

"countPaths"函数在每一步被递归调用两次，在本例中有两个BASE条件，其作用是阻止递归函数无休止地执行（即两个IF语句）。
每次执行时，创建2个新的嵌套调用（D AND R）（path），递增i或j ...除非满足其中一个条件。然后使用返回值的总和计算总路径。
像这样：