Activación de una recursión en java

Question

La recursión es una especie de estilo 'divide y vencerás', se divide mientras se hace más pequeño (estructura de datos de árbol) y quiero que se rompa por completo si se encuentra una infracción, lo que significa ruptura todos los caminos recursivos, y devuelve verdadero. es posible?

Answer 1

Puede devolver un código de error o modificar alguna variable global para que cada instancia recursiva sepa "suicidarse".

Algo del género.

int foo(bar){ 
    int to_the_next; 

     if (go_recursive){ 
      to_the_next = foo(whisky_bar); 

      if (to_the_next ==DIE) return DIE; 
     } 

     if (something_unexpected_happened) return DIE; 

     process;//may include some other recursive calls, etc etc 
} 

Answer 2

Puede hacer algo similar almacenando una variable que rastree si las recursiones se deben romper o no. Tendría que comprobarlo lamentablemente cada recursión, pero puede hacerlo.

Answer 3

Si se trata de un único hilo que realiza la recursión, podría lanzar una excepción. Sin embargo, es un poco feo: algo así como usar una excepción como un goto.

boolean myPublicWrapperMethod(...) { 
    try { 
     return myPrivateRecursiveFunction(...); 
    } catch (MySpecificException e) { 
     return true; 
    } 
} 

Un mejor enfoque sería eliminar la recursividad y utilizar un conjunto de pila de una clase que representa lo que habría sido el estado recursiva, iterar en un bucle y sólo devuelve verdadero cuando lo desee.

Answer 4

A menos que las llamadas recursivas se evalúen en paralelo, probablemente solo necesite agregar algo de lógica para verificar el primer valor de la llamada recursiva antes de realizar la segunda (y subsiguiente, si no es una estructura de árbol binario) llamada recursiva.

public abstract class Tree { 

    protected abstract boolean headIsViolation(); 

    protected abstract boolean isLeaf(); 

    public Tree getLeft(); 

    public Tree getRight(); 

    // Recursive 
    public boolean checkViolation() { 
     if(this.isLeaf()) { 
      return this.headIsViolation(); 
     } 

     // If needed, you could pass some sort of 'calculation state' 
     // object through the recursive calls and evaluate the violation 
     // through that object if the current node is insufficient 
     if(this.headIsViolation()) { 
      // Terminate the recursion 
      return true; 
     } 

     // Fortunately, Java short-circuits || 
     // So if the left child is in violation, the right child will 
     // not even be checked 
     return this.getLeft().checkViolation() || this.getRight().checkViolation(); 
    } 
} 

Answer 5

No importa lo que hagas, vas a tener que desconectar la pila. Esto deja dos opciones:

1. valor de retorno mágico (como se describe por uno de los Toms)
2. lanzar una excepción (como se ha mencionado por thaggie)

Si el caso en el que desea que las cosas mueren es raro, esta puede ser una de esas situaciones donde arrojar una excepción podría ser una opción viable. Y antes de que todos se metan en la garganta, recuerde que una de las reglas más importantes de programación es saber cuándo es apropiado romper la regla.

Como resultado, pasé hoy evaluando la biblioteca zxing del código de google. En realidad usan lanzamientos de excepción para muchas estructuras de control. Mi primera impresión cuando lo vi fue horror. Literalmente llamaban a métodos decenas de miles de veces con diferentes parámetros hasta que el método no arrojaba una excepción.

Esto ciertamente parecía un problema de rendimiento, así que hice algunos ajustes para cambiar las cosas a usar un valor de retorno mágico. ¿Y sabes qué? El código era un 40% más rápido cuando se ejecutaba en un depurador. Pero cuando cambié a no depuración, el código era menos de 1% más rápido.

Todavía no estoy loco por la decisión de usar excepciones para el control de flujo en este caso (es decir, las excepciones se lanzan todos los el tiempo). Pero ciertamente no vale la pena el tiempo para volver a implementarlo dada la diferencia de rendimiento casi inconmensurable.

Si su condición que desencadena la muerte de la iteración no es una parte fundamental del algoritmo, usar una excepción puede hacer que su código sea mucho más limpio.Para mí, el punto donde tomaría esta decisión es si la recursión completa debe ser desenrollada, entonces usaría una excepción. SI solo se debe desenrollar parte de la recursión, use un valor de retorno mágico.

Answer 6

Lo que está preguntando es la definición de recursividad.

En algún punto, todas las rutas recursivas deberían romperse. De lo contrario, se producirá una recursión infinita y se producirá stack overflow exception.

Entonces debería diseñar la función de recursión así. Un ejemplo binary search in a sorted array:

BinarySearch(A[0..N-1], value, low, high) { 
     if (high < low) 
      return -1 // not found 
     mid = low + ((high - low)/2) // Note: not (low + high)/2 !! 
     if (A[mid] > value) 
      return BinarySearch(A, value, low, mid-1) 
     else if (A[mid] < value) 
      return BinarySearch(A, value, mid+1, high) 
     else 
      return mid // found 
} 

Answer 7

lo recomiendo un tratamiento de excepciones. Con ella se precisa, que la recursividad fue abortado debido a alguna violación (o otra excepción):

public void outer() { 
    try { 
    int i = recurse(0); 
    } catch (OuchException ouch) { 
    // handle the exception here 
    } 
} 

private int recurse(int i) throws OuchException { 

    // for tree-like structures 
    if (thisIsALeaf) { 
     return i; 
    } 

    // the violation test 
    if (itHurts) 
     throw new OuchException("That really hurts"); 

    // we also can encapsulate other exceptions 
    try { 
     someMethod(); 
    } catch (Exception oops) { 
     throw new OuchException(oops); 
    } 

    // recurse 
    return recurse(i++); 
}

Claro, se viola el requisito inicial para volver 'verdadero' sobre el aborto. Pero prefiero una separación limpia de los valores de retorno y una notificación sobre el comportamiento anormal.

Answer 8

Pude salir de todas las llamadas recursivas usando una variable global.

boolean skipRecursivePaths = false; 
private callAgain(){ 

if(callAgain){ 
    if(getOutCompletely){ 

    skipRecursivePaths = true; 
    } 
    if(skipRecursivePaths){ 
    return; 
    } 
} 

Answer 9

La mejor manera de salir de un bucle recursivo cuando se detecta un error es lanzar una excepción de tiempo de ejecución.

throw new RuntimeException("Help! Somebody debug me! I'm crashing!"); 

Por supuesto, esto mata a su programa, pero usted debe emplear la verificación del rango y el análisis algoritmo para asegurarse de que su recursividad no produce una excepción. Una de las razones por las que podría querer salir de un algoritmo recursivo es que se está quedando sin memoria. Aquí, es posible determinar cuánta memoria usará tu algoritmo en la pila. Si está codificando Java, por ejemplo, comparar ese cálculo a

getMemoryInfo.availMem(). 

Digamos que usted está utilizando la recursividad para encontrar n !. Su función es como la siguiente:

public long fact(int n) 
{ 
    long val = 1; 
    for (int i = 1, i<=n,i++) 
     return val *= fact(i); 
    return val; 
} 

Antes de que lo ejecute, compruebe que tiene (número de bytes en un largo, 8 en Java) * n bytes de memoria para contener toda la pila. Básicamente, con el rango y la verificación de errores antes del método/función recursiva, no debería necesitar salir. Dependiendo de tu algoritmo, sin embargo, es posible que debas indicarle a toda la pila que eres bueno para ir. Si ese es el caso, la respuesta de Tom funciona.

Answer 10

mejor tener una matriz booleana

de esa manera no hay un estado mundial

if(stop[0]) return; 

Answer 11

Tal vez usted quiere evitar la repetición y sustituirla por una pila. Esto le da el control para salir de la operación, mientras que puede hacer algo que se asemeja a una operación recursiva. De hecho, solo emuláis la recursión por ti mismo.

encontré una buena explicación aquí: http://haacked.com/archive/2007/03/04/Replacing_Recursion_With_a_Stack.aspx/