Comment garder un compte "choses faites" dans un algorithme récursif en Java?

Question

J'ai un algorithme récursif qui parcourt une chaîne, caractère par caractère, et l'analyse pour créer une structure arborescente. Je veux être capable de garder une trace de l'index des caractères que l'analyseur est actuellement (pour les messages d'erreur tout autant que toute autre chose) mais je ne tiens pas à implémenter quelque chose comme un tuple pour gérer plusieurs types retournés.

J'ai essayé d'utiliser un type Integer, déclaré en dehors de la méthode et passé dans la méthode récursive, mais parce qu'il est final, les incréments d'appels récursifs sont "oubliés" quand je reviens. (Parce que l'incrémentation de la valeur Integer rend le point de référence de l'objet transmis par un nouvel objet)

Existe-t-il un moyen de faire fonctionner quelque chose qui ne pollue pas mon code?

Answer 1

Puisque vous avez déjà découvert l'entier pseudo-mutable « hack », que diriez-vous cette option:

Est-il judicieux pour vous de faire une classe Parser séparée? Si vous faites cela, vous pouvez stocker l'état actuel dans une variable membre. Vous avez probablement besoin de réfléchir à la façon dont vous allez gérer les problèmes de sécurité des threads, et cela pourrait être exagéré pour cette application particulière, mais cela pourrait fonctionner pour vous.

Answer 2

C'est un peu un hack, mais parfois j'utilise un AtomicInteger, qui est mutable, pour faire des choses comme ça. J'ai aussi vu des cas où un int [] de taille 1 est passé dans

Answer 3

La solution actuelle, je me sers est:.

int[] counter = {0}; 

et passer ensuite à l'algorithme récursif:

public List<Thing> doIt (String aString, int[] counter) { ... } 

et quand je veux incrémenter:

counter[0]++; 

Pas super élégant, mais il fonctionne ...

Answer 4

Les entiers sont immuables, ce qui signifie que lorsque vous le transmettez en tant qu'argument, il crée une copie plutôt qu'une référence au même élément. (explanation). Pour obtenir le comportement que vous recherchez, vous pouvez écrire votre propre classe qui est comme Integer seulement modifiable. Ensuite, passez-la à la fonction récursive, elle est incrémentée dans la récursivité, et quand vous y accédez à nouveau après la fin de la récursivité, elle conservera ses nouvelles valeurs. Edit: Notez que l'utilisation d'un tableau int [] est une variante de cette méthode ... En Java, les tableaux sont également transmis par référence plutôt que copiés comme des primitives ou des classes immuables.

Answer 5

Pour être honnête, je recoderais la fonction pour en faire un algorithme linéaire qui utilise une boucle. De cette façon, vous n'avez aucune chance de manquer d'espace de tas si vous traversez une chaîne extrêmement grande. De plus, vous n'avez pas besoin d'avoir un paramètre supplémentaire juste pour garder une trace du nombre.

Cela aurait également pour résultat de rendre l'algorithme plus rapide car il n'a pas besoin de faire un appel de fonction pour chaque caractère.

Sauf bien sûr, il y a une raison spécifique pour laquelle il doit être récursif.

Answer 6

Une possibilité que je peux penser est de stocker le compte dans une variable membre de la classe.Cela suppose bien sûr que la méthode publique doIt est appelée uniquement par un seul thread.

Une autre option consiste à refactoriser la méthode publique pour appeler une méthode d'assistance privée. La méthode privée prend la liste en paramètre et renvoie le nombre. Par exemple:

public List<Thing> doIt(String aString) { 
    List<Thing> list = new ArrayList<Thing>(); 
    int count = doItHelper(aString, list, 0); 
    // ... 
    return list; 
} 

private int doItHelper(String aString, List<Thing> list, int count) { 
    // ... 
    // do something that updates count 
    count = doItHelper(aString, list, count); 
    // ... 
    return count; 
} 

Cela suppose que vous pouvez faire l'erreur de manipulation dans la méthode doIt publique, puisque la variable count n'est pas réellement passé à l'appelant. Si vous avez besoin de faire cela, vous pouvez bien sûr lancer une exception:

public List<Thing> doIt(String aString) throws SomeCustomException { 
    List<Thing> list = new ArrayList<Thing>(); 
    int count = doItHelper(aString, list, 0); 
    // ... 
    if (someErrorOccurred) { 
     throw new SomeCustomException("Error occurred at chracter index " + count, count); 
    } 
    return list; 
} 

Il est difficile de savoir si cela va aider sans en savoir plus sur la façon dont votre algorithme fonctionne réellement.

Answer 7

Vous pouvez simplement utiliser une variable de classe static int qui s'incrémente chaque fois que votre méthode doIt est appelée.

Answer 8

Vous pouvez également faire:

private int recurse (int i) { 

    if (someConditionkeepOnGoing) { 
     i = recurse(i+1); 
    } 

    return i; 
}