java - 即使有基本情况，我的代码也会导致 StackOverflowError

Question

我正在编写一个类，该类旨在递归地跟踪下限和上限，并通过在到达上限值后返回下限值来对之间的所有值求和。例如调用

System.out.println(sum(2, 5));

应返回 23，因为这是 2 + 3 + 4 + 5 + 4 + 3 + 2 的总和。

以下是我解决此问题的代码。即使有基本情况，由于第 15 行和第 17 行的递归调用，我仍然收到 StackOverflowError。

public static int sum(int lower, int upper)
{
    int total = (upper - lower) + (upper - lower) + 1;
    return sum(lower, upper, total);
}

public static int sum(int lower, int upper, int total)
{
    if (lower < upper)
        return lower + sum(lower + 1, upper, total - 1);
    else if (lower == upper)
        return lower + sum(lower - 1, upper, total - 1);
    else if (total == 0)
        return 0;
    return 0;
}

public static void main(String[] args) 
{
    System.out.println(sum(2, 5));
}

有人可以帮我找出 StackOverflow 的原因并纠正它吗？

Answer 1

因此，lower 为 2，upper 为 5。

if (lower < upper)
    return lower + sum(lower + 1, upper, total - 1);

此条件成立，因此您可以使用 lower==3 和 upper==5 调用 sum。
这将使用 lower==4 和 upper==5 调用 sum。
这将使用 lower==5 和 upper==5 调用 sum。

这次你打了

else if (lower == upper)
    return lower + sum(lower - 1, upper, total - 1);

这将使用 lower==4 和 upper==5 调用 sum。再次。

这给你一个无限递归。一旦 lower 达到 upper，您就将其减一，因此它会不断上下翻转 1。

如何解决这个问题？

如果您必须通过递归来完成此操作，您可以简单地编写如下内容:

public static int sum(int lower, int upper) {
    // shouldn't happen, but in case you pass in weird arguments
    if (lower > upper) {
        return 0;
    }
    if (lower==upper) {
        return upper;
    }
    return 2*lower + sum(lower+1, upper);
}

因此对于 sum(2,5) 你得到

sum(2,5) = 2*2 + sum(3,5)
         = 2*2 + 3*3 + sum(4,5)
         = 2*2 + 2*3 + 2*4 + sum(5,5)
         = 2*2 + 2*3 + 2*4 + 5
         = 2 + 3 + 4 + 5 + 4 + 3 + 2