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

Question

J'ai une fonction qui s'appelle récursivement, et je veux détecter et terminer si elle entre dans une boucle infinie, c'est-à-dire être à nouveau appelée pour le même problème. Quelle est la meilleure façon de faire cela?

EDIT: Ceci est la fonction, et elle sera appelée récursivement avec des valeurs différentes 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, à savoir qu'il n'a pas d'effets d'état ou sur le côté, vous pouvez garder un Set des arguments (modifier: voir votre édition, vous garderait un ensemble de paires de (x, y)) qu'il a été appelé avec, et chaque fois il suffit de vérifier si l'argument actuel est dans l'ensemble. De cette façon, vous pouvez détecter un cycle si vous le rencontrez rapidement. Mais si l'espace d'argument est grand et que la répétition prend du temps, 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 parce que c'est le problème d'arrêt.

Answer 2

Une façon est de passer une variable depth d'un appel à l'autre, incrémenter chaque fois que votre fonction elle-même appelle. Vérifiez que depth 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

Un moyen facile serait de mettre en œuvre une des opérations suivantes:

passer la valeur précédente et la nouvelle valeur à l'appel récursif et faire votre première étape, une vérification pour voir si elles sont la même chose - c'est peut-être votre cas récursif. Passez une variable pour indiquer le nombre de fois que la fonction a été appelée, et limitez arbitrairement le nombre de fois qu'elle peut être appelée.

Answer 4

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 5

On dirait que vous travaillez sur un tableau 2D. Si vous avez un peu plus à perdre dans les valeurs du tableau, vous pouvez l'utiliser comme un drapeau. Vérifiez-le et terminez la récursion si le drapeau a été défini. Ensuite, réglez-le avant de continuer.

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

Answer 6

Vous pouvez seulement détecter les plus triviaux en utilisant l'analyse de programme. Le mieux que vous pouvez faire est d'ajouter des gardes dans votre situation particulière et passer un contexte de niveau de profondeur. Il est presque impossible de détecter le cas général et de différencier l'utilisation légitime des algorithmes récursifs.

Answer 7

Vous devrez trouver une solution de rechange, car comme vous l'avez demandé, il n'y a pas de solution générale. Voir le Halting problem pour plus d'informations.

Answer 8

Vous pouvez utiliser la surcharge pour une signature cohérente (ce qui 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; 
} 

réponse de John Kugelman avec surcharge est mieux beacuse il est thread-safe, alors que statique les variables ne le sont pas.

Billy3

Answer 9

à mon humble avis boucles ne peut aller dans une boucle infinie.

Si votre méthode a trop de niveau de récursivité la machine virtuelle Java lancera une StackOverflowError. Vous pouvez intercepter cette erreur avec un bloc try/catch et faire ce que vous avez l'intention de faire lorsque cette condition se produit.