递归实现迷宫(0,0)到(n,m)路径数计算的原理求解

先明确问题：这段代码是计算从**(0,0)到(n-1,m-1)**的有效路径数（代码里的终点判断是i==n-1 && j==m-1），移动规则仅允许向右或向下走一步。

代码核心逻辑拆解 #

1. 终止条件 #

• 当i==n或j==m：说明走到网格边界外，这条路径无效，返回0。
• 当i==n-1 && j==m-1：刚好到达终点，这条路径有效，返回1。

2. 递归核心 #

当前位置(i,j)的总路径数 = 向下走一步到(i+1,j)的路径数 + 向右走一步到(i,j+1)的路径数。
道理很直白：从当前点出发，所有路径要么先向下走，要么先向右走，把这两种方向的所有可能路径数相加，就是当前点的总路径数。

拿n=3、m=3的例子一步步走 #

咱们从最初的countPaths(0,0,3,3)开始拆解，帮你理清执行流程：

1. 第一次调用：countPaths(0,0,3,3)
   不满足任何终止条件，先计算downPath = countPaths(1,0,3,3)，再计算rightPath = countPaths(0,1,3,3)，最终返回两者之和。

2. 计算downPath：countPaths(1,0,3,3)

   • 不满足终止条件，先算downPath = countPaths(2,0,3,3)：
     • 进入countPaths(2,0,3,3)：
       • downPath = countPaths(3,0,3,3) → 触发i==n，返回0。
       • rightPath = countPaths(2,1,3,3)：
         • 进入countPaths(2,1,3,3)：
           • downPath = countPaths(3,1,3,3) → 返回0。
           • rightPath = countPaths(2,2,3,3) → 到达终点，返回1。
           • 因此countPaths(2,1,3,3)返回0+1=1。
       • 因此countPaths(2,0,3,3)返回0+1=1。
   • 再算rightPath = countPaths(1,1,3,3)：
     • 进入countPaths(1,1,3,3)：
       • downPath = countPaths(2,1,3,3) → 已算出返回1。
       • rightPath = countPaths(1,2,3,3)：
         • 进入countPaths(1,2,3,3)：
           • downPath = countPaths(2,2,3,3) → 返回1。
           • rightPath = countPaths(1,3,3,3) → 返回0。
           • 返回1+0=1。
       • 因此countPaths(1,1,3,3)返回1+1=2。
   • 因此countPaths(1,0,3,3)返回1+2=3。

3. 计算rightPath：countPaths(0,1,3,3)（你疑惑的部分）

   • 不满足终止条件，先算downPath = countPaths(1,1,3,3) → 已算出返回2。
   • 再算rightPath = countPaths(0,2,3,3)：
     • 进入countPaths(0,2,3,3)：
       • downPath = countPaths(1,2,3,3) → 已算出返回1。
       • rightPath = countPaths(0,3,3,3) → 触发j==m，返回0。
       • 返回1+0=1。
   • 因此countPaths(0,1,3,3)返回2+1=3。

4. 回到最初调用
   countPaths(0,0,3,3)返回3+3=6，这就是最终输出的结果。

简单总结：递归就是把大问题拆成无数个相同逻辑的小问题，直到碰到终止条件得到明确结果，再把这些结果一步步向上累加，最终得到起点的总路径数。

内容的提问来源于stack exchange，提问作者Strange Alchemist