count += countPaths(sp + i, ep) 的值是如何计算的?

问题描述 投票:0回答:1

代码的输出是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;
    }
}

我尝试对代码进行空运行以了解其工作原理、堆栈框架,尤其是如何计算该值?但我想不出这个,所以我需要这些方面的指导。

java counting
1个回答
0
投票

不清楚你要什么。以下是给定执行如何产生值 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
© www.soinside.com 2019 - 2024. All rights reserved.