while 循环中的递归函数如何在 Java 中工作？

Question

我在 google 上找到了这段代码，但我找不到递归部分的实际工作原理。该代码是关于在有向图上找到 2 个顶点之间的可能路径。这是打印总可能路径的方法：

public void  total_path(int source, int destination)
{
  result = 0;
  boolean[] visit = new boolean[size];
  for(int i = 0; i < size; i++)
  {
    visit[i] = false;
  }
  count_path(source, destination, visit);
  System.out.println(result);
}

这里是计算所有可能路径的递归方法：

  public void  count_path(int start, int end, boolean[] visit)
     {
              if(start > size || end > size || start < 0 || end < 0 || node == null)
              {
                return ;
              }
        
              if(visit[start]==true)
              {
                return;
              }
        
              if(start == end)
              {
                 result = result + 1;
              }
              
              visit[start] = true;
              AjlistNode temp = node[start].next;
        
              while(temp!=null)
              {
                count_path(temp.id, end, visit); 
                temp = temp.next;
              }
              
              visit[start]=false;
     }

这是我创建的图表：

g.addEdge(0, 1); 
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 5);
g.addEdge(3, 4);
g.addEdge(4, 2);
g.addEdge(4, 5);
g.addEdge(5, 6);

我已经编译了 运行 起点是 0 终点是 6 的程序。结果是 3，已经在 YouTube 上查找了算法，但我仍然不明白如何可视化以及代码如何在 while 循环内的递归部分流动。

Answer 1

递归函数必须包含 return 值的基本情况，而不是递归调用的结果。在这种情况下：

if(start > size || end > size || start < 0 || end < 0 || node == null)
{
    return;
}
    
if(visit[start]==true)
{
    return;
}

是那些会破坏递归调用链的基本情况。请记住，方法 count_path returns void。如果该方法需要 return 某个值，您会看到那些 if 块 returning 某种默认值。例如，当您看到递归斐波那契的示例时，输入值 Fib(0) 和 Fib(1) return 的基本情况。否则，它 return 是（累积）递归调用的结果。

这些基本情况是什么？

该方法计算从当前节点到某个目标节点的路径数。因此，如果节点已经被访问过（因此应该已经计算出路径）只需 return 而不重新计算。另外，如果你的图中只有一个节点，或者没有节点，那么就没有路径（所以 return 没有计算）。

为什么答案是 3 条路径？

下图是基于添加边的调用。每个条目都是从起始节点到结束节点的单向路径。因此，从节点 0 开始，要到达节点 6，共有 3 条路径，它们已在附图中列出。