Recursive function taking ages to run

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 reac开发者_运维技巧hing 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

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

If you want to refactor a recursive function to an iterative one the steps are as follows:

1) Determine the base case of the Recursion. Base case, when reached, causes Recursion to end. Every Recursion must have a defined base case. In addition, each recursive call must make a progress towards the base case (otherwise recursive calls would be performed infinitely).
2) Implement a loop that will iterate until the base case is reached.
3) Make a progress towards the base case. Send the new arguments to the top of the loop instead to the recursive method.

Example of how trying to understand what it is doing can make the code faster/simpler...

This method is trying to determine if 'n' is a multiple of 4 or n+1 is a multiple of 4. This can be written much shorter as.

private static boolean condition(int n){
    return (n+1) & 3 <= 1;
}

To convert this to an iterative form, note that you are computing a function on two (discrete) variables. You can use a table to store the values of the function, and fill in the table in a specific order so that you have already computed values you need by the time you need them. (in this case, from higher values of x and y).

In this case, the boundary cases (corresponding to the base cases in the original recursion) are:

f(7, y..5), f(8, 6)
f(x..5, 7), f(6, 8)
f(7, 7)

Then we fill in f(7, 6) and f(6, 7) and then proceed "downwards" - i.e. f(6, 6), f(5, 6) ... f(x, 6), f(6, 5), f(5, 5) ... f(x, 5) ... f(x, y).

Note that what looks like function call syntax corresponds to a table lookup (it really converts to array syntax).