Recursive function taking ages to run

Question

I profiled my code and found that my program spent roughly 85% of the time executing this particular recursive function. The function aims to calculate the probability of reaching a set of states in a markov chain, given an initial position (x,y).

private static boolean condition(int n){
    int i = 0;
    while ( n >= i){
        if( n == i*4 || n == (i*4 - 1))
            return true;
            i++;
        }
    return false;
}

public static double recursiveVal(int x, int y, double A, double B){

    if(x> 6 && (x- 2 >= y)){ return 1;}
    if(y> 6 && (y- 2 >= x)){ return 0;}
    if(x> 5 && y> 5 && x== y){ return (A*(1-B) / (1 -(A*B) - ((1-A)*(1-B))));}

    if(condition(x+ y)){
        return (recursiveVal(x+1, y,A,B)*A + recursiveVal(x, y+1,A,B)*(1-A));
    }
    else{
        return (recursiveVal(x+1, y,A,B)*(1-B) + recursiveVal(x,y+1,A,B)*B);
    }
}

I was once told that 99% of recursive functions could be replaced by a while loop. I'm having trouble doing this though. Does anyone know how I could improve the execution time or rewrite this as a iterative loop?

Thanks

Answer 1

You could try to use a technique called memoization which basically caches previously computed results for recursive calls.

• Wikipedia article on memoization.

As a side note, I recommend reformatting your code a bit. Here is a simplified version of yoru code.

private static boolean condition(int n){
    for (int i = 0; i <= n; i++)
        if(n == i*4 || n == (i * 4 - 1))
            return true;
    return false;
}

public static double recursiveVal(int x, int y, double A, double B){

    if (x > 6 && (x - 2 >= y))
        return 1;

    if (y > 6 && (y - 2 >= x))
        return 0;

    if(x > 5 && y > 5 && x == y)
        return A*(1-B) / (1 -(A*B) - ((1-A)*(1-B)));

    double val1 = recursiveVal(x+1, y, A, B);
    double val2 = recursiveVal(x, y+1, A, B);

    return condition(x + y)
        ? A * val1 + val2 * (1-A)
        : (1-B) * val1 + B * val2; 
}