StackOverflowError運行我的「騎士之旅」時（它幾乎完成了其他情況）

我試圖製作一個程序，通過棋盤的所有方塊（大小並不重要，但現在它是6x6）與騎士，稱爲「騎士之旅」check it out on wiki。StackOverflowError運行我的「騎士之旅」時（它幾乎完成了其他情況）

該旅程應該是關閉的，這意味着最後一個被訪問的廣場上的騎士可以「攻擊」他開始的廣場。該代碼對於某些方塊工作正常，例如，main中的輸入「遍歷（1,1,1）」生成輸出，不僅顯示他正在遍歷但回溯並且成功回溯到朝向目標的遍歷。但是，我會輸入'遍歷（1,0,0）'，我得到一個StackOverflowError。由於它有時成功，回溯和遍歷，我知道代碼的作品，我只是不知道如何擺脫錯誤。我假設我打了太多的電話，但我不知道如何解決這個問題，有很多方塊可以訪問:) 編輯了代碼，主要是因爲老師可以找到我說的一個騙子。

來源

2011-03-05 XistenZ

也許我今天有太多的巧克力，但它看起來像'traverse（1,0,0）'應該立即返回。 – 2011-03-05 01:57:21

你實現了哪種算法？我強烈建議您閱讀您提供的同一個wiki頁上提出的解決方案。分而治之的使用多項式時間。 – UmNyobe 2012-01-30 12:24:00

您正試圖解決遞歸的指數複雜性問題。這是非常小的投入以外的工作。堆棧大小的增長速度比問題的大小更快。它不會需要很大的問題才能通過堆棧。

你不會讓StackOverflowErrors消失。您需要重新將您的算法視爲基於循環而不是基於遞歸的算法。

來源

2011-03-05 01:45:40

這聽起來像是一種應該花費大量時間的方法，你的意思是說，當用遞歸解決問題時，在它被簡單標記爲「不可能用遞歸求解」之前有最大量的選擇，並且被迫使用循環代替？ – XistenZ 2011-03-05 14:54:42

這是正確的。每個堆棧幀花費資源。您無法分配過多的堆棧幀來解決問題，因爲您將很快耗盡系統資源。由於指數複雜性問題，您甚至無法使用更多硬件啓用遞歸解決方案，因爲所需的堆棧幀數量比問題大小指數增長要快。通過比較，循環不需要每次迭代的額外資源。 – 2011-03-05 16:43:22

@ user645621：在Java中，是的，但它不是遞歸的固有問題。就我所見，算法中的遞歸完全由尾部調用組成（即你的函數以函數調用結束）。 *如果* JVM做了尾部調用優化，這個特定的解決方案不會消耗比循環更多的堆棧空間，因爲編譯器會將尾部調用轉換爲跳轉。換句話說，如果您在Scheme（或Erlang，或其他語言與TCO）中重寫它，它會運行。 – molbdnilo 2011-03-05 21:07:33

StackOverflowError運行我的「騎士之旅」時（它幾乎完成了其他情況）

回答

相關問題