Comment détecter une boucle infinie dans un appel récursif?

J'ai une fonction récursive appelant elle-même, et je tiens à les détecter et d'y mettre fin si entre dans une boucle infinie, je.e - appelé pour le même problème à nouveau. Quelle est la meilleure façon de le faire?

EDIT: C'est la fonction, et elle sera appelée récursivement avec différentes valeurs de x et y. je veux résilier si dans un appel récursif, la valeur de la paire (x,y) est répétée.

int fromPos(int [] arr, int x, int y)

OriginalL'auteur Pranav | 2009-06-23

9

Si la fonction est purement fonctionnel, c'est à dire qu'il n'a pas d'état ou des effets secondaires, alors vous pouvez garder une Set des arguments (edit: voir votre modification, vous devez garder un Ensemble de couples (x,y) ) qu'il a été appelé avec, et à chaque fois, il suffit de vérifier si l'argument courant est dans le jeu. De cette façon, vous pouvez détecter un cycle si vous exécutez en elle assez rapidement. Mais si l'argument de l'espace est grand et il faut beaucoup de temps pour se rendre à une répétition, vous risquez de manquer de votre mémoire avant de détecter un cycle. En général, bien sûr, vous ne pouvez pas le faire, car c'est le problème de l'arrêt.

ouais, vient de réaliser son le problème de l'arrêt. Peut-être que je devrais mettre une prime sur elle. 😀
Cette méthode ne permet pas de détecter si il est légal pour la fonction à appeler parfois lui-même avec les mêmes valeurs, tandis que la profondeur de récursivité méthode peut fonctionner pour le cas général.
Oh, et il exige que les frais généraux de la construction de l'ensemble et les inscriptions qui y figurent.
N'oubliez pas de vider l'ensemble quand vous avez fini.
J'ai dit "si la fonction n'a pas d'état ou des effets secondaires" (je devrais aussi ajouter "et ne dépend d'aucune extérieure de l'état"); dans ce cas, il n'est pas acceptable pour une fonction à appeler lui-même avec les mêmes valeurs

OriginalL'auteur newacct
20

Une façon est de passer un depth variable d'un appel à l'autre, en augmentant à chaque fois que votre fonction s'appelle elle-même. Vérifiez que depth ne pas dépasser certains seuils. Exemple:
```
int fromPos(int [] arr, int x, int y)
{
    return fromPos(arr, x, y, 0);
}

int fromPos(int [] arr, int x, int y, int depth)
{
    assert(depth < 10000);

    //Do stuff

    if (condition)
        return fromPos(arr, x+1, y+1, depth + 1);
    else
        return 0;
}
```
Putain! Tu m'as devancé!
+1 me Battre aussi.
Je préfère, si la signature de la méthode reste la même.
Suffit d'utiliser la surcharge de fournir un arrière compatible signature.
Dans ce cas, vous secrètement appeler une 2ème fonction de la profondeur de l'argument. Voir la réponse révisée.

OriginalL'auteur John Kugelman
3

Vous aurez besoin de trouver un travail, parce que comme vous l'avez demandé, il n'y a pas de solution générale. Voir la Problème de l'arrêt pour plus d'info.

OriginalL'auteur JP Alioto
2

Un moyen simple serait de mettre en œuvre l'une des opérations suivantes:

Passer de l'ancienne valeur et la nouvelle valeur de l'appel récursif et faire votre première étape a vérifier pour voir si elles sont de la même - c'est peut-être votre récursive cas.

Passer une variable pour indiquer le nombre de fois que la fonction a été appelée, et de façon arbitraire de limiter le nombre de fois où il peut être appelé.

OriginalL'auteur Relster
2

Vous ne pouvez détecter la plupart insignifiants à l'aide de l'analyse du programme. Le meilleur que vous pouvez faire est d'ajouter les gardes dans votre cas particulier et de passer à un niveau de profondeur contexte. Il est presque impossible de détecter le cas général, et de différencier l'utilisation légitime des algorithmes récursifs.

OriginalL'auteur ojblass

Vous pouvez soit utiliser la surcharge pour une signature (c'est la meilleure méthode), ou vous pouvez utiliser une variable statique:

int someFunc(int foo)
{
    static recursionDepth = 0;
    recursionDepth++;
    if (recursionDepth > 10000)
    {
        recurisonDepth = 0;
        return -1;
    }
    if (foo < 1000)
        someFunc(foo + 3);
    recursionDepth = 0;
    return foo;
}

Jean Kugelman, en réponse à la surcharge est mieux car c'est thread-safe, tandis que les variables statiques sont pas.

Billy3

OriginalL'auteur Billy ONeal

0

Ressemble, vous pouvez travailler sur un tableau 2D. Si vous avez un bit supplémentaire de rechange dans les valeurs de la matrice, vous pouvez l'utiliser comme un drapeau. Cochez la case, et mettre fin à la récursivité si l'indicateur a été défini. Puis il avant de continuer.

Si vous n'avez pas un peu de ménage dans les valeurs, vous pouvez toujours faire un tableau d'objets à la place.

Cela a été utile, merci.

OriginalL'auteur patros

Si vous voulez garder votre signature de la méthode, vous pouvez garder un couple de jeux pour enregistrer les valeurs de x et de y.

static Set<Integer> xs;
static Set<Integer> ys;//Initialize this!
static int n=0;//keeps the count function calls.

int fromPos(int [] arr, int x, int y){

 int newX= getX(x);
 int newY= getY(y);
 n++; 
 if ((!xs.add(Integer.valueOf(newX)) && !ys.add(Integer.valueOf(newY))){

   assert(n<threshold); //threshold defined elsewhere.
   fromPos(arr,newx,newy);
 }
}

Qu'en est-il quand elle ne se répète dans le prochain appel, mais après quelques intervenir des appels?
Vous êtes de droite. l'édition
Serait downvoter commentaire?

OriginalL'auteur Tom

0

À mon humble avis, Seuls les boucles peuvent aller dans une boucle infinie.

Si votre méthode a trop de niveau de récursivité de la JVM va jeter un StackOverflowError. Vous pouvez intercepter cette erreur avec un bloc try/catch et faire ce que vous comptez faire, lorsque cette condition se produit.

OriginalL'auteur Peter Lawrey
0

Une fonction récursive se termine dans le cas où une condition est remplie.

Exemples:
- Le résultat d'une fonction est 0 ou est 1
- Le nombre maximal d'appels est atteint
- Le résultat est inférieur/supérieur à la valeur d'entrée
Dans votre cas, la condition est ([x0,y0] == [xN,yN]) OR ([x1,y1] == [xN,yN]) OR ([xN-1,yN-1] == [xN,yN])

0, 1, ...N sont les indices des paires

Donc vous avez besoin d'un conteneur(vector, list, map) pour stocker toutes les précédentes paires et de les comparer à la paire actuelle.

OriginalL'auteur Th. Thielemann

De la première utilisation mvn findbugs:interface graphique pour ouvrir un gui qui point à la ligne où cette erreur est présente.

J'ai aussi été confronté au même problème et je l'ai résolu en ajoutant une variable booléenne dans la boucle de vérification.

Code avant de l' ->

for (local = 0; local < heightOfDiv; local = local + 200) { //Line under Error
          tileInfo = appender.append(tileInfo).append(local).toString();
          while (true) {
            try {
              tileInfo = appender.append(tileInfo).append(getTheTextOfTheElement(getTheXpathOfTile(incr))).toString();
              incr++;
            } catch (Exception e) {
              incr = 1;
              tileInfo = appender.append(tileInfo).append("/n").toString();
            }
          }

Pour Résoudre ce problème, j'ai juste ajouté une variable booléenne et le mettre à false dans le bloc catch. Check it down

for (local = 0; local < heightOfDiv; local = local + 200) {
          tileInfo = appender.append(tileInfo).append(local).toString();
          boolean terminationStatus = true;
          while (terminationStatus) {
            try {
              tileInfo = appender.append(tileInfo).append(getTheTextOfTheElement(getTheXpathOfTile(incr))).toString();
              incr++;
            } catch (Exception e) {
              incr = 1;
              tileInfo = appender.append(tileInfo).append("/n").toString();
              terminationStatus = false;
            }
          }

C'est comment j'ai Résolu ce problème.
Espérons que cela aidera. 🙂

OriginalL'auteur AKASH DUBEY

Vous devez vous connecter pour publier un commentaire.