Menu
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
866
Recursion is slower and it consumes more memory since it can fill up the stack. But there is a work-around called tail-call optimization which requires a little more complex code (since you need another parameter to the function to pass around) but is more efficient since it doesn't fill the stack.
The simplicity of recursion comes at the cost of time and space efficiency. It is much slower than iteration due to the overhead of function calls and control shift from one function to another. It requires extra memory on the stack for each recursive call.
The big-O runtime for a recursive function is equivalent to the number of recursive function calls. This value varies depending on the complexity of the algorithm of the recursive function. For example, a recursive function of input N that is called N times will have a runtime of O(N).
This case—when the function completes without making a recursive call—is called the base case. If a recursion never reaches a base case, it will go on making recursive calls forever and the program will never terminate. This is known as infinite recursion, and it is generally not considered a good idea.
You could try to use a technique called memoization which basically caches previously computed results for recursive calls.
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 love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
