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

Question

J'ai une fonction qui s’appelle elle-même de manière récursive, et je veux détecter et mettre fin si elle passe dans une boucle infinie, c’est-à-dire être appelée à nouveau pour le même problème. Quel est le moyen le plus simple de le faire?

EDIT: C'est la fonction, et elle sera appelée de manière récursive avec différentes valeurs de x et y. Je veux terminer 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)

Answer 1

Si la fonction est purement fonctionnelle, c'est-à-dire qu'elle n'a pas d'état ni d'effet secondaire, vous pouvez conserver un ensemble d'arguments (édition: voir votre édition, vous conserverez un ensemble de paires de (x, y)) avec lequel il a été appelé, et à chaque fois, vérifiez si l’argument en cours est dans l’ensemble. De cette façon, vous pouvez détecter un cycle si vous le rencontrez assez rapidement. Mais si l'espace d'argument est grand et qu'il faut beaucoup de temps pour répéter, vous risquez de manquer de 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 qui nous stoppe.

Answer 2

L’une des méthodes consiste à transmettre une variable profondeur d’un appel à l’autre, en l’incrémentant à chaque appel de votre fonction. Vérifiez que profondeur ne dépasse pas un certain seuil. 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;
}

Answer 3

Vous aurez besoin de trouver une solution de rechange, car comme vous l'avez demandé, il n'y a pas de solution générale. Consultez le problème de blocage pour plus d'informations.

Answer 4

Un moyen simple consiste à implémenter l’un des éléments suivants:

Transmettez la valeur précédente et la nouvelle valeur à l'appel récursif et vérifiez le premier pas pour voir si elles sont identiques - il s'agit peut-être de votre cas récursif.

Passez une variable pour indiquer le nombre d'appels de la fonction et limiter le nombre d'appels de manière arbitraire.

Answer 5

Vous ne pouvez détecter que les plus insignifiants à l'aide d'une analyse de programme. Le mieux que vous puissiez faire est d'ajouter des protecteurs dans votre cas particulier et de passer au contexte de niveau de profondeur. Il est presque impossible de détecter le cas général et de distinguer l'utilisation légitime d'algorithmes récursifs.

Answer 6

Vous pouvez utiliser la surcharge pour une signature cohérente (c'est la meilleure méthode) ou 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;
}

La réponse de John Kugelman à la surcharge est préférable, car elle est thread-safe, contrairement aux variables statiques.

Billy3

Answer 7

On dirait que vous travaillez sur un tableau 2D. Si vous avez un petit extra à consacrer aux valeurs du tableau, vous pouvez l'utiliser comme indicateur. Vérifiez-le et mettez fin à la récursivité si l'indicateur a été défini. Puis définissez-le avant de continuer.

Si vous n'avez pas beaucoup de ressources dans les valeurs, vous pouvez toujours en faire un tableau d'objets.

Answer 8

Si vous souhaitez conserver la signature de votre méthode, vous pouvez conserver quelques ensembles pour enregistrer les anciennes valeurs de x et 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);
 }
}

Answer 9

Seules les boucles IMHO peuvent aller dans une boucle infinie.

Si votre méthode a trop de niveaux de récursivité, la machine virtuelle Java génère une erreur StackOverflowError. Vous pouvez intercepter cette erreur avec un bloc try / catch et faire ce que vous souhaitez faire lorsque cette situation se produit.

Answer 10

Une fonction récursive se termine si une condition est remplie.

Exemples:

• Le résultat d'une fonction est 0 ou 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]) OU ([x1, y1] == [xN, yN]) OU ([xN-1, yN- 1] == [xN, yN])

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

Vous avez donc besoin d’un conteneur (vecteur, liste, carte) pour stocker toutes les paires précédentes et les comparer à la paire actuelle.

Answer 11

Commencez par utiliser mvn findbugs: gui pour ouvrir un gui qui pointe vers la ligne où cette erreur est présente.

J'ai également rencontré le même problème et je l'ai résolu en ajoutant une variable booléenne à la vérification de la boucle.

Code avant - >

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, je viens d'ajouter une variable booléenne et de la définir sur false dans le bloc catch. Vérifiez-le

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

Voici comment j'ai résolu ce problème. J'espère que cela aidera. :)