代码的输出是4。函数在循环中被递归调用。 count += countPaths(sp + i, ep) bieng 的值如何计算?如何递归调用函数?堆栈框架是什么?
// Count the number of paths possible from start point to end point in game board
public class CountPaths {
public static void main(String[] args) {
System.out.println(countPaths(0, 3));
}
private static int countPaths(int sp, int ep) {
if (sp == ep) {
return 1;
}
if (sp > ep) {
return 0;
}
int count = 0;
for (int i = 1; i <= 6 ; i++) {
count += countPaths(sp + i, ep);
}
return count;
}
}
我尝试对代码进行空运行以了解其工作原理、堆栈框架,尤其是如何计算该值?但我想不出这个,所以我需要这些方面的指导。
不清楚你要什么。以下是给定执行如何产生值 4 的演练。
来自
main
的调用的初始状态将传递终止状态并进入循环,该循环进行 6 次递归调用并返回它们的总和。所以它正在执行以下操作(为了便于阅读,将方法名称简化为 x
):
x(0,3) = x(1,3) + x(2,3) + x(3,3) + x(4,3) + x(5,3) + x(6,3)
查看您的终端条件 - 即您不进行递归的情况。
if (sp == ep) {
return 1;
}
if (sp > ep) {
return 0;
}
终止条件为给定执行定义以下情况: x(4+, 3) = 0 x(3,3) = 1
鉴于这些知识,我们可以将基本案例简化为以下内容:
x(0,3) = x(1,3) + x(2,3) + 1 + 0 + 0 + 0
= x(1,3) + x(2,3) + 1
对这两种情况进行类似的练习(即
x(1,3)
、x(2,3)
)。
x(1,3) = x(2,3) + x(3,3) + x(4,3) + x(5,3) + x(6,3) + (7,3)
= x(2,3) + 1 + 0 + 0 + 0 + 0
= x(2,3) + 1
x(2,3) = x(3,3) + x(4,3) + x(5,3) + x(6,3) + x(7,3) + x(8,3)
= 1 + 0 + 0 + 0 + 0 + 0
= 1
我们解决了 x(2,3),因此我们将其代入 x(0,3) 和 x(1,3)...
x(0,3) = x(1,3) + x(2,3) + 1 + 0 + 0 + 0
= x(1,3) + 1 + 1
= x(1,3) + 2
x(1,3) = x(2,3) + x(3,3) + x(4,3) + x(5,3) + x(6,3) + (7,3)
= x(2,3) + 1 + 0 + 0 + 0 + 0
= 1 + 1 + 0...
= 2
我们解决了 x(1,3),因此我们可以将其代入 x(0,3),然后我们就完成了..
x(0,3) = x(1,3) + x(2,3) + 1 + 0 + 0 + 0
= 2 + 1 + 1
= 4