java - 通过在递归方法中将 1 加到 N/2 并将 N/2 加到 N 来计算和 1 到 N

Question

我在制作计算 1,2,3 到 N 之和的递归方法时遇到问题，但是通过将 (1,2,3... 到 N/2) 与 (N/2+1) 相加来实现... 到 N)。

到目前为止我管理的代码是这样的:

public static void main(String[] args) {

    System.out.println(sum(10, 1));
}

public static int sum(int n, int start) {

    if (start == n){
        return n;
    }

    if (start > n / 2){
        return start + sum(n, start + 1);
    }

    return start + sum(n, start + 1);

}

我认为这是错误的，这是学校的一项作业，我们必须激发将递归拆分成多个部分是计算总和的效率更高/更低的方法。 (将数字从 1 加到 N/2 与 N/2 加到 N，而不是直接从 1 到 N)。

他让我们这样做是为了让我们更难，但我根本无法理解如何做到这一点。这是对的吗？

谢谢

Answer 1

在某些情况下可能有助于减少递归深度。

在计算内部步骤的 n/2 时需要考虑开始，代码可能看起来类似于:

public static int sum(int n, int start) {
  if (start > n) {
    return 0;
  }

  if (start == n){
      return n;
  }

  int n2 = (start + n) / 2;
  return sum(n2, start) + sum(n, n2 + 1);
} 

对于 start 和 n 相差小于 2 的情况，start > n 检查只是避免了最后的额外检查。