我的代碼甚至導致了一個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案件

回答

相關問題