Recursive function taking ages to run

Question

Hice un perfil de mi código y descubrí que mi programa pasó aproximadamente el 85% del tiempo ejecutando esta función recursiva en particular. La función tiene como objetivo calcular la probabilidad de alcanzar un conjunto de estados en una cadena de markov, dada una posición inicial (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); 
    } 
} 

Una vez me dijeron que el 99% de las funciones recursivas podrían reemplazarse por un ciclo while. Sin embargo, estoy teniendo problemas para hacer esto. ¿Alguien sabe cómo podría mejorar el tiempo de ejecución o reescribir esto como un ciclo iterativo?

Gracias

Answer 1

usted podría tratar de utilizar una técnica llamada memoization que básicamente almacena en caché los resultados previamente calculados para llamadas recursivas.

• Wikipedia article on memoization.

Como nota al margen, recomiendo volver a formatear el código un poco. Aquí hay una versión simplificada del código yoru.

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

Answer 2

Para convertir esto a una forma iterativa, tenga en cuenta que está calculando una función en dos variables (discretas). Puede usar una tabla para almacenar los valores de la función y completar la tabla en un orden específico para que ya haya calculado los valores que necesita para el momento en que los necesita. (en este caso, desde valores más altos de x y y).

En este caso, los casos de contorno (que corresponden a los casos base en la recursión original) son:

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

Entonces llenamos en f(7, 6) y f(6, 7) y luego proceder "hacia abajo" - es decir f (6 , 6), f (5, 6) ... f (x, 6), f (6, 5), f (5, 5) ... f (x, 5) ... f (x, y)

Tenga en cuenta que lo que parece una sintaxis de llamada de función corresponde a una búsqueda de tabla (realmente se convierte en sintaxis de matriz).

Answer 3

Si desea refactorizar una función recursiva a un proceso iterativo los pasos son los siguientes:

1) Determinar el caso base de la recursividad. El caso base, cuando se alcanza, hace que la Recursividad termine. Cada Recursión debe tener un caso base definido. Además, cada llamada recursiva debe avanzar hacia el caso base (de lo contrario, las llamadas recursivas se realizarían infinitamente).
2) Implementar un ciclo que iterará hasta que se alcance el caso base.
3) Avance hacia la carcasa base. Envíe los nuevos argumentos al principio del ciclo en lugar del método recursivo.

Answer 4

Ejemplo de cómo tratar de entender lo que está haciendo puede hacer que el código más rápido/más simple ...

Este método está tratando de determinar si 'n' es un múltiplo de 4 o n + 1 es un múltiplo de 4. Esto se puede escribir mucho más corto que.

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