rupture d'un récursivité en java

Question

La récursion est une sorte de style « diviser pour mieux régner », il se sépare tout en obtenant plus petite (structure de données d'arbre), et je le veux briser complètement si une violation est constatée, ce qui signifie la rupture tous les chemins récursifs, et retour vrai. Est-ce possible?

Answer 1

Vous pouvez renvoyer un code d'erreur, ou modifier une variable globale de sorte que chaque instance récursive sait « se tuer ».

Quelque chose du genre.

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

Vous pouvez faire quelque chose de similaire en stockant une variable qui suit si les récurrences devraient briser ou non. Il faudrait malheureusement vérifier chaque récursion, mais vous pouvez le faire.

Answer 3

Si c'est un seul thread faire la récursion, vous pouvez lancer une exception. Peu moche si - sorte d'utiliser une exception comme un goto.

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

Une meilleure approche serait d'éliminer la récursion et utiliser une collection Stack tenue d'une classe représentant ce qui aurait été l'état récursif, itérer dans une boucle et juste revenir vrai quand vous voulez.

Answer 4

À moins que les appels récursifs soient évalués en parallèle, il suffit probablement d'ajouter une logique pour vérifier la valeur du premier appel récursif avant d'effectuer le second appel récursif (et éventuellement un arbre binaire).

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

Peu importe ce que vous faites, vous allez devoir dérouler la pile. Cela laisse deux options:

1. valeur de retour magique (tel que décrit par l'un des Toms)
2. Throw une exception (comme mentionné par thaggie)

Si le cas où vous voulez que les choses meurent est rare, cela peut être une de ces situations où lancer une exception peut être un choix viable. Et avant que tout le monde me saute à la gorge, rappelez-vous que l'une des règles de programmation les plus importantes est de savoir quand il est approprié d'enfreindre la règle.

Comme il se trouve, j'ai passé l'évaluation aujourd'hui la bibliothèque ZXing de code Google. Ils utilisent réellement des jets d'exception pour beaucoup de structures de contrôle. Ma première impression quand je l'ai vu était horreur. Ils appelaient littéralement les méthodes des dizaines de milliers de fois avec des paramètres différents jusqu'à ce que la méthode ne lance pas d'exception.

Cela ressemblait certainement un problème de performance, donc je fait quelques ajustements pour changer les choses sur à l'aide d'une valeur de retour magique. Et tu sais quoi? Le code était 40% plus rapide lors de l'exécution dans un débogueur. Mais quand je suis passé au non-débogage, le code était moins de 1% plus rapide.

Je ne suis toujours pas fou de la décision d'utiliser des exceptions pour le contrôle de flux dans ce cas (je veux dire, les exceptions sont jetés tout le temps). Mais cela ne vaut certainement pas la peine de le ré-implémenter compte tenu de la différence de performance presque incommensurable.

Si votre condition qui déclenche la mort de l'itération est pas un élément fondamental de l'algorithme, en utilisant une exception peut rendre votre code un beaucoup plus propre.Pour moi, le point où je prendrais cette décision est que si toute la récursion doit être annulée, alors j'utiliserais une exception. SI seule une partie de la récursion doit être déroulée, utilisez une valeur de retour magique.

Answer 6

Ce que vous demandez, c'est la définition de la récursivité.

À un certain point, tous les chemins récursifs devraient se rompre. Sinon, ce sera une récursion infinie et stack overflow exception se produit.

Donc, vous devriez concevoir la fonction de récursion comme ça. Un exemple 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

Je recommanderais une gestion des exceptions. Cela indique clairement, que la récursivité a été annulée en raison d'une violation (ou autre exception):

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

Bien sûr, il viole l'exigence initiale de revenir « vraie » sur l'avortement. Mais je préfère une séparation nette des valeurs de retour et une notification sur les comportements anormaux.

Answer 8

J'ai été capable de quitter tous les appels récursifs en utilisant une variable globale.

boolean skipRecursivePaths = false; 
private callAgain(){ 

if(callAgain){ 
    if(getOutCompletely){ 

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

Answer 9

La meilleure façon de sortir d'une boucle récursive lorsqu'une erreur est rencontrée est de lancer une exception d'exécution.

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

Bien sûr, cela tue votre programme, mais vous devez utiliser l'analyse de la vérification et de l'algorithme gamme pour vous assurer que votre récursion ne jette pas une telle exception. Une raison pour laquelle vous pourriez vouloir sortir d'un algorithme récursif est que vous manquez de mémoire. Ici, il est possible de déterminer la quantité de mémoire que votre algorithme utilisera sur la pile. Si vous codez Java, par exemple, comparer ce calcul à

getMemoryInfo.availMem(). 

Disons que vous utilisez récursion pour trouver n !. Votre fonction ressemble à ceci:

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

avant de l'exécuter, vérifiez que vous avez (nombre d'octets dans une longue, 8 en Java) * n octets en mémoire pour maintenir l'ensemble de la pile. Fondamentalement, avec la vérification de distance et d'erreur avant la méthode/fonction récursive, vous ne devriez pas avoir besoin de sortir. Selon votre algorithme, cependant, vous devrez peut-être signaler à toute la pile que vous êtes prêt à partir. Si c'est le cas, la réponse de Tom fonctionne.

Answer 10

mieux d'avoir un tableau booléen

cette façon il n'y a pas état global

if(stop[0]) return; 

Answer 11

Peut-être que vous voulez éviter la récursivité et le remplacer par une pile. Cela vous donne le contrôle de sortir de l'opération, tout en étant capable de faire quelque chose qui ressemble à une opération récursive. En fait, vous ne faites qu'émuler la récursivité par vous-même.

J'ai trouvé une explication bien ici: http://haacked.com/archive/2007/03/04/Replacing_Recursion_With_a_Stack.aspx/