Comment comptabiliser les « 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 pouvoir garder une trace de l'index de caractères auquel se trouve actuellement l'analyseur (pour les messages d'erreur autant que pour toute autre chose), mais je ne souhaite pas implémenter quelque chose comme un tuple pour gérer plusieurs types renvoyé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 comme il est final, les incréments d'appel récursifs sont "oubliés" à mon retour.(Parce que l'incrément de la valeur entière fait que le point de référence de l'objet passé par valeur est un nouvel objet)

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

Answer 1

Puisque vous avez déjà découvert le "hack" des entiers pseudo-mutables, que diriez-vous de cette option :

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

Answer 2

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

Answer 3

La solution actuelle que j'utilise est la suivante :

int[] counter = {0};

puis transmettez-le à l'algorithme récursif :

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

et quand je veux l'incrémenter :

counter[0]++;

Pas super élégant, mais ça marche...

Answer 4

Les entiers sont immuables, ce qui signifie que lorsque vous les transmettez en argument, cela crée une copie plutôt qu'une référence au même élément.(explication).

Pour obtenir le comportement que vous recherchez, vous pouvez écrire votre propre classe qui est comme Integer uniquement mutable.Ensuite, transmettez-le simplement à la fonction récursive, il est incrémenté dans la récursion, et lorsque vous y accéderez à nouveau une fois la récursion terminée, il conservera toujours ses nouvelles valeurs.

Modifier: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

Vous pouvez simplement utiliser une variable de classe int statique qui est incrémentée à chaque fois que votre méthode doIt est appelée.

Answer 6

Vous pourriez également faire :

private int recurse (int i) {

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

    return i;
}

Answer 7

Pour être honnête, je recoderais la fonction pour en faire un algorithme linéaire utilisant une boucle.De cette façon, vous n'avez aucune chance de manquer d'espace de stockage si vous parcourez une chaîne extrêmement volumineuse.De plus, vous n’auriez pas besoin d’un paramètre supplémentaire uniquement pour suivre le décompte.

Cela aurait également probablement 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.

À moins bien sûr qu’il y ait une raison spécifique, cela doit être récursif.

Answer 8

Une possibilité à laquelle je peux penser est de stocker le nombre dans une variable membre de la classe.Cela suppose bien sûr que le public doIt La méthode n’est appelée que 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 comme 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 puissiez effectuer la gestion des erreurs en public doIt méthode, puisque le count la variable n'est pas réellement renvoyée à l'appelant.Si vous devez le faire, vous pouvez bien sûr lever 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 sera utile sans en savoir plus sur le fonctionnement réel de votre algorithme.