Summing within a recursion

Question

Summing within a recursion: Does it always produce a StackOverflow Error?

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;
}

I get that error for the line:

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

Is there any creative solution?

Answer 1

I would recommend using a dynamic programming approach. This way values are never calculated a second time, and you don't need to worry about a stack overflow.

Create a t by N array.

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

From here you sum all of the elements of the previous row and multiply by A[k][i] and B[i][O[0] - 1] where k is the index of the row of the previous column and i is the index of the row of the current column.

For the final result you need to use the value of i that you originally called it with.

This way you only are doing 2*t multiplications and t*N*N summations. significantly less than what you are doing now.

If you need help with the actual implementation you should look up the veterbi algorithm. It is quite similar.