java - 使用递归修改求和

Question

如何使用递归定义修改求和方法，通过 - (1 to N/2) + (( N/2+1) 到 N)？我在这里有点困惑，我已经输入了一些类似的东西，但这不是递归:

public static int Sum(int n){
    int sum1 = 0;
    int sum2 = 0;
    int totalSum = 0;
    for(int i = 1; i <= n/2; i++){
        sum1 += i;
    }
    for(int i = n/2 + 1; i <= n; i++){
        sum2 += i;
    }
    totalSum = sum1 + sum2;
    return totalSum;
}

Answer 1

首先，您的实现不是递归的。

您的问题说明了正确的算法:要对 1 和 n 之间的值求和，您可以对 1 和 n/2 之间的值求和，然后在 n 之间求和/2 + 1 和 n。这意味着我们需要创建一个辅助函数 sum(int a, int b) 其目标是返回 a 和 b 之间所有值的总和。

• 基本情况是 a == b:在这种情况下，助手应该只返回 a。
• 在递归步骤中，我们执行前面的算法:从 a 求和到 (a+b)/2 并从 (a+b) 求和/2 + 1 到 b。

这将是一个实现:

public static int sum(int a, int b) {
    if (a == b) {
        return a;
    }
    int middle = (a + b) / 2;
    return sum(a, middle) + sum(middle + 1, b);
}

有了这个，初始任务变成:

public static int sum(int n) {
    return sum(1, n);
}

一些示例:

public static void main(String[] args) {
    System.out.println(sum(4)); // prints 10
    System.out.println(sum(5)); // prints 15
    System.out.println(sum(6)); // prints 21
}