编写一个函数（递归）计算从 1 到 n 的偶数之和

Question

我必须编写一个递归函数来计算从 1 到 n 的偶数之和。例如 n=input= 6 预期的 output would be: 2+4+6 = 12

 def sum_of_even(n):
    if not n % 2 == 0:
        return n
    else:
        return n + sum_of_even(n-1)

print(sum_of_even(6))

这给出了输出 11，但我什至不知道我的概念是否正确

原文由 randomobject123 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

对代码进行最少的修改：

 def sum_of_even(n):
    if n==0:
        return 0
    if not n % 2 == 0:
        return sum_of_even(n-1)
    else:
        return n + sum_of_even(n-1)

print(sum_of_even(10))

您的代码有两个问题：

1. 当数字为偶数时，您没有返回到目前为止计算的值。相反，您返回的是输入值 n。通过这样做，您只是简单地总结到之前的 n 值 value n + sum_of_even(n-1) 。因此，当您 print(sum_of_even(6)) 它返回 6 + sum_of_even(6-1) 即 11。如果您 print(sum_of_even(5)) 它只会返回 5。

2. 由于上述停止条件不正确，您需要一个合适的停止条件。你想添加所有偶数直到零（而不是 -inf ），所以：

 if n==0:
    return 0

编辑：或者，Stef 建议，当您找到第一个偶数时，您可以简单地移动 2 乘 2 而不是 1 乘 1 次：

 def sum_of_even(n):
    if n<=0:
        return 0
    if not n % 2 == 0:
        return sum_of_even(n-1)
    else:
        return n + sum_of_even(n-2)

原文由 willcrack 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

我会推荐一种分而治之的方法，其基础是可以通过将前半个范围的总和与后半个范围的总和相加来找到整个范围内的总和。对于每个递归调用，这将子问题的大小分成两半，而不是一次减少一个。其他提议的解决方案将耗尽输入大于 2000 的递归堆栈，而这种方法适用于巨大的数字。

 def sum_of_even(upperlim, lowerlim = 2):
    if upperlim <= lowerlim:
        if upperlim == lowerlim:
            return upperlim
        else:
            return 0
    midpoint = lowerlim + (upperlim - lowerlim) // 2
    if midpoint % 2 == 0:
        return sum_of_even(upperlim, midpoint + 2) + sum_of_even(midpoint, lowerlim)
    else:
        return sum_of_even(upperlim, midpoint + 1) + sum_of_even(midpoint - 1, lowerlim)

def cross_check(n):
    half_n = n // 2
    return half_n * (half_n + 1)

n = 1000000
print(sum_of_even(n))   # => 250000500000
print(cross_check(n))   # => 250000500000

如您所见，我还提供了一个 cross_check 例程来确认答案。这是基于观察到偶数值的总和高达 n 等于 2*(1 + 2 + ... + n // 2) 。 （请注意，无论 n 是偶数还是奇数，这都是正确的。）直到 k 的整数之和是众所周知的结果， k * (k + 1) / 2 因此，为 --- 插入 n // 2 k ，并注意到 2 的取消，我们得到了 cross_check 中的公式——这实际上应该是你使用的——的递归。

原文由 pjs 发布，翻译遵循 CC BY-SA 4.0 许可协议