在递归内求和

在递归内求和：它是否总是产生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

在递归内求和

回答

相关问题