我的代码甚至导致了一个StackOverflowError案件

我正在编写一个类，用于递归追踪下限和上限，并通过返回上限值后返回到下限值来总结中间的所有值。例如调用我的代码甚至导致了一个StackOverflowError案件

System.out.println（sum（2，5））;

应返回23，因为这是2 + 3 + 4 + 5 + 4 + 3 + 2

以下是我的代码针对此问题的总和。即使有一个基本情况，我仍然得到的StackOverflowError由于上线15递归调用和17

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上的原因，然后纠正它？

来源

2017-05-30 Aero

使用调试器，找出发生了什么 – Jens

这是一个无限递归....下降永远不会比上限更大。 – Nidhoegger

如果下面的解决方案解决了您的问题，您可能想要接受该解决方案。 – user3437460

所以，lower是2和upper是5

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

这种情况是真实的，所以你打电话sum与lower==3和upper==5。
这将调用sum与lower==4和upper==5。
这将调用sum与lower==5和upper==5。

这个时候你打

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

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

这给你一个无限递归。 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

来源

2017-05-30 13:35:28 khelwood

OP可以通过添加一个表示它是否上升的标志来解决这个问题。例如'sum（int lower，int upper，int total，boolean isAscending）' – Michael

非常感谢这个回应。这真的帮了我很多。 – Aero

不客气。这里有一个接受答案按钮。 – khelwood

我的代码甚至导致了一个StackOverflowError案件

回答

相关问题