在遞歸內求和

在遞歸內求和：它是否總是產生StackOverflow錯誤？在遞歸內求和

public final static float getAlpha(int t, int i, int N, float[] P, float[][] B, float[][] A, int[] O) 
{ 
    float alpha; 
    if (t==1) 
    { 
     alpha = P[i] * B[i][O[0] - 1]; 
    } 
    else 
    { 
     float sum = 0; 
     int k; 
     for (k=0; k < N; k++){ 
      sum = sum + (getAlpha(t-1, k, N, P, B, A, O) * A[k][i]); 
     } 
     alpha = sum * B[i][O[0] - 1]; 
    } 
    return alpha; 
}

我得到的錯誤行：

sum = sum + (getAlpha(t-1, k, N, P, B, A, O) * A[k][i]);

有任何創造性的解決方案？

來源

2013-05-10 LanneR

'StackOverflow'將始終發生，如果您的遞歸是**無限**。 – 2013-05-10 23:11:16

N有多大？小N發生？ – arynaq 2013-05-10 23:15:08

T是否可能作爲非正數開始？即如果t = 0，它不會終止。 – user949300 2013-05-10 23:16:16

顯然你的t很大（或者有一個錯誤，它小於1）。因此，除非您可以重寫此函數以進行尾遞歸（難點，因爲遞歸發生在循環中），並且您正在運行正確類型的執行尾遞歸的JVM（實際上只有少數幾個實例），遞歸解決方案總是會溢出堆棧。

在這一點上，我會建議嘗試以迭代方式重寫它。這可能意味着從底部開始，並將中間值存儲在數組中。

來源

2013-05-10 23:21:23 ILMTitan

只是爲了澄清一下，我的「非常大」我認爲你說的是100,000左右，對吧？我從來沒有爲大N做過那麼多的遞歸工作，但我認爲大多數JVM應該有足夠的內存來進行數千次遞歸。注意：我認爲N不太重要，因爲你會先發生。 – user949300 2013-05-10 23:26:57

我更想的是10000左右，但我並不真誠地知道。它可能不僅取決於JVM，還取決於堆棧幀的大小。 – ILMTitan 2013-05-10 23:35:41

對不起，目前的代碼不會工作。每當它被遞歸地調用時，我都會變化。你需要一個'txN'數組。 – placeybordeaux 2013-05-10 23:48:58

它在我看來，你不必要地重新計算相同的價值一次又一次。你的遞歸遵循一個樹形模式，其中每個分支都是相同的，並且這些分支的每個子分支都是相同的，等等。所涉及的計算量是指數級地大於它應該是的。

來源

2013-05-10 23:35:20

雖然這可能是真的，但它不會是一個計算器的原因。這隻會是表現不佳的原因。 – ILMTitan 2013-05-10 23:46:30

公平點。但是如果最初的't'足夠大，導致堆棧溢出，那麼這個程序在宇宙熱量死亡之前可能無法完成運行。 – 2013-05-10 23:52:48

我會推薦使用動態編程方法。這種方式的值不會再次計算，並且您不必擔心堆棧溢出。

用N數組創建一個t。

所以Array[i][0] = P[i] * B[i][O[0] - 1]

從這裏你總結以前的所有行的元素，並通過A[k][i] and B[i][O[0] - 1]乘以其中k是前一列和i的行的索引是當前列的行索引。

對於最終結果，您需要使用最初調用它的值i。

這種方式，你只是在做2*t乘法和t*N*N總結。比現在做的要少得多。

如果您需要實際實施方面的幫助，您應該查看veterbi算法。它非常相似。

來源

2013-05-10 23:56:24 placeybordeaux

在遞歸內求和

回答

相關問題