C++矩阵路径求解代码中findPaths函数为何打印path后递减i、j?
3×3矩阵路径搜索中坐标回退(i/j递减)的技术原理
你观察到的“打印完路径后i、j出现递减”的现象,是深度优先递归搜索配合回溯逻辑的正常运行表现,不是代码bug。
核心本质:递归栈帧的压入与弹出
常规实现的findPaths递归逻辑如下,所有坐标变化都是围绕栈帧生命周期展开的:
// 输入参数:当前所在坐标(i,j),全局共享的路径存储vector void findPaths(int i, int j, vector<pair<int,int>>& path) { // 当前坐标存入路径 path.push_back({i, j}); // 递归终止:到达右下角终点 if (i == 2 && j == 2) { printPath(path); path.pop_back(); // 弹出终点坐标,准备回溯 return; } // 优先尝试向右移动 if (isvalid(i, j+1)) { findPaths(i, j+1, path); } // 再尝试向下移动 if (isvalid(i+1, j)) { findPaths(i+1, j, path); } // 当前坐标所有可走方向都遍历完成,弹出坐标准备回溯 path.pop_back(); }
- 递归调用的内存模型是独立栈帧:每次调用
findPaths(i, j+1)时,程序会在栈上创建一个新的函数执行上下文,这个上下文里的i、j参数是独立于外层栈帧的,不会修改外层的变量值。 - 当深层递归的任务执行完成(比如走到终点打印完路径),函数就会执行return,释放当前栈帧,程序的执行点就会回到上一层的调用位置,这时候拿到的当前活跃坐标,就是上一层栈帧里保存的原始i、j值。
坐标“递减”的具体发生过程
举一条典型路径的遍历过程,就能直观看到坐标变化的逻辑:
- 从起点(0,0)出发,一路向右走到(0,2),再一路向下走到(2,2),打印完这条合法路径
- (2,2)的栈帧执行return,程序回到上一层的(2,1)栈帧——此时当前坐标从(2,2)变回(2,1),j值从2降到1,这是你观察到的第一次“j递减”
- (2,1)的栈帧尝试完所有合法方向(向右到终点、向下越界),执行return回到上一层的(1,1)栈帧——此时坐标从(2,1)变回(1,1),i值从2降到1,这就是你看到的“i递减”
常见认知误区:很多人误以为i、j是全局变量被手动修改,才会出现递减。实际上i、j只是每个栈帧的局部参数,根本不存在“被某个代码块写小”的过程——所谓的递减,只是程序逐层从深层递归返回时,当前上下文切换回上层栈帧的参数值带来的视觉效果。
和路径vector的同步关系
你在代码里对path vector的push、pop操作,和栈帧的压入、弹出是完全对齐的:
- 每压入一层新栈帧,就往path里push当前坐标
- 每弹出一层栈帧(return回溯),就从path里pop对应坐标
如果出现pop时机不对(比如在递归终止时忘了pop、在函数末尾忘了pop),就会导致path的长度和栈帧深度不匹配,很多人会把这种路径错乱的问题,误判为“i、j变量莫名递减”。
内容的提问来源于stack exchange,提问作者fadao838
相关产品推荐
相关产品推荐

