一個神祕的計算器錯誤？

-1

我只是做了熱身，我偶然發現了這一點：一個神祕的計算器錯誤？

三種方法之間的區別是我如何添加到啓動參數的遞歸調用。

我最初解決它與列出的第二個函數，但它給了我臭名昭着的stackoverflow錯誤。第一個不給我一個stackoverflow錯誤。這個網站有什麼問題，或者是否存在差異1和2，即微妙的Java語言片段？

public boolean groupSum(int start, int[] nums, int target) { 
    if (start >= nums.length) 
     return (target == 0); 

    return groupSum(start+1, nums, target - nums[start]) || groupSum(start+1,  
     nums, target); 
}

------------這些原因在流誤差堆--------------

public boolean groupSum(int start, int[] nums, int target) { 
    if (start >= nums.length) 
     return (target == 0); 

    return groupSum(start++, nums, target - nums[start]) || groupSum(start++,  
     nums, target); 
} 

public boolean groupSum(int start, int[] nums, int target) { 
    if (start >= nums.length) 
     return (target == 0); 

    return groupSum(++start, nums, target - nums[start]) || groupSum(++start,  
     nums, target); 
}

來源

2013-05-31 LLL

有沒有什麼神祕的stackoverflow錯誤，它只是意味着你的遞歸方法從未停止。爲什麼？可能是因爲基礎案例的錯誤設計。另外，請不要說這隻發生在Java *中，它也可能發生在其他編程語言上。 –

我也意識到這些函數是如何失效的，因爲它們具有O（2^n）的複雜性。我正在做一個面試的熱身，需要練習遞歸。 – LLL

這三個函數都具有相同的基本情況。他們只是在我如何添加開始不同。我會澄清這個問題。 – LLL

++start（稱爲預增）評估爲start+1。 start++（稱爲後增量，因爲在增量完成後評估）評估爲start。它們都將變量中的值設置爲start+1作爲評估的副作用。所以，當你做start++時，你將start傳遞給方法的下一個調用，它將start傳遞給方法的下一個調用......你永遠不會達到基本情況，並且無限遞歸。

來源

2013-05-31 05:55:06 Patashu

使用++ start也會導致一個stackoverflow。我最初也是這麼想的。它可能只是網站上的一個錯誤。 – LLL

@LLL我不相信。（我也不認爲它可能是網站上的一個bug，它會使用與你相同的編譯器。） – Patashu

我給你鏈接到該網站;）我非常擅長查找錯誤。這是一個詛咒。 – LLL

這是一個臭名昭着的微妙的錯誤。看看這個遞歸調用：

groupSum(start++, nums, target - nums[start])

注意，你是通過start++作爲第一個參數。這將使用後綴++運營商，其執行以下操作：

增量start，然後
返回所用start值有。

換句話說，這將更新的start的本地副本是start + 1，再通start舊值到遞歸調用。這意味着start從不會因呼叫而改變，所以基本情況從不觸發，因此堆棧溢出。您可以通過在函數頂部添加一個System.out.println聲明來確認這一點。

這裏可能還有其他問題，但我懷疑這是你的罪魁禍首。

希望這會有所幫助！

來源

2013-05-31 05:55:26 templatetypedef

這並不能解釋爲什麼它在++啓動時失敗:) – LLL

@LuiggiMendoza不正確。 ++ start返回start + 1，所以它不應該遞歸無限。 – Patashu

@Patashu你是對的。現在評估給出一個SOE的'++ start'的原因。 –

一個神祕的計算器錯誤？

回答

相關問題