CODEWITHSUNDEEP
javarecursion
user1830307
user1830307

Reputation:

Summing within a recursion

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?

Upvotes: 3

Views: 167

Answers (3)

placeybordeaux
placeybordeaux

Reputation: 2216

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.

Upvotes: 2

James Holderness
James Holderness

Reputation: 23031

It looks to me ike you're unnecessarily recalculating the same values over and over again. Your recursion is following a tree pattern where every branch is the same, and every sub branch of those branches are the same, etc. So the amount of calculation involved is exponentially larger than it should be.

Upvotes: 0

ILMTitan
ILMTitan

Reputation: 11037

Clearly your t is very large (or there is a mistake and it is less than 1).

So, unless you can rewrite this function to have tail recursion (difficult, given that the recursion happens in a loop), and you are running on the correct type of JVM that does tail recursion (only a few actually do), a recursive solution is always going to overflow the stack.

At this point, I would suggest trying to rewrite it in an iterative fashion. This probably means starting from the bottom up, and storing intermediate values in an array.

Upvotes: 0

Related Questions