¿Cómo mantener un recuento de "cosas hechas" en un algoritmo recursivo en Java?

Question

Tengo un algoritmo recursivo que recorre una cadena, carácter por carácter, y la analiza para crear una estructura similar a un árbol.Quiero poder realizar un seguimiento del índice de caracteres en el que se encuentra actualmente el analizador (tanto para mensajes de error como para cualquier otra cosa), pero no estoy interesado en implementar algo como una tupla para manejar múltiples tipos devueltos.

Intenté usar un tipo Integer, lo declaré fuera del método y lo pasé al método recursivo, pero debido a que es final, los incrementos de llamada recursiva se "olvidan" cuando regreso.(Porque el incremento del valor entero hace que la referencia del objeto pasado por valor apunte a un nuevo objeto)

¿Hay alguna manera de hacer que funcione algo similar que no contamine mi código?

Answer 1

Como ya has descubierto el "truco" de enteros pseudomutables, ¿qué tal esta opción?

¿Tiene sentido para usted crear una clase Parser separada?Si hace esto, puede almacenar el estado actual en una variable miembro.Probablemente necesites pensar en cómo vas a manejar cualquier problema de seguridad de subprocesos, y puede que sea excesivo para esta aplicación en particular, pero podría funcionar para ti.

Answer 2

Es una especie de truco, pero a veces uso un AtomicInteger, que es mutable, para hacer cosas como esta.También he visto casos en los que se pasa un int[] de tamaño 1.

Answer 3

La solución actual que estoy usando es:

int[] counter = {0};

y luego pasarlo al algoritmo recursivo:

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

y cuando quiero incrementarlo:

counter[0]++;

No es muy elegante, pero funciona...

Answer 4

Los números enteros son inmutables, lo que significa que cuando los pasa como argumento, crea una copia en lugar de una referencia al mismo elemento.(explicación).

Para obtener el comportamiento que está buscando, puede escribir su propia clase que sea como Integer solo mutable.Luego, simplemente páselo a la función recursiva, se incrementa dentro de la recursividad y cuando acceda nuevamente después de que finalice la recursividad, aún mantendrá sus nuevos valores.

Editar:Tenga en cuenta que usar una matriz int[] es una variación de este método...En Java, las matrices también se pasan por referencia en lugar de copiarse como clases primitivas o inmutables.

Answer 5

Podrías usar una variable de clase int estática que se incrementa cada vez que se llama a tu método doIt.

Answer 6

También puedes hacer:

private int recurse (int i) {

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

    return i;
}

Answer 7

Para ser honesto, recodificaría la función para convertirla en un algoritmo lineal que utiliza un bucle.De esta manera, no tendrá ninguna posibilidad de quedarse sin espacio en el montón si recorre una cadena extremadamente grande.Además, no necesitaría tener un parámetro adicional solo para realizar un seguimiento del recuento.

Esto probablemente también tendría el resultado de hacer que el algoritmo sea más rápido porque no necesita realizar una llamada de función para cada carácter.

A menos, por supuesto, que haya una razón específica por la que deba ser recursivo.

Answer 8

Una posibilidad que se me ocurre es almacenar el recuento en una variable miembro de la clase.Por supuesto, esto supone que el público doIt El método solo es llamado por un único hilo.

Otra opción es refactorizar el método público para llamar a un método auxiliar privado.El método privado toma la lista como parámetro y devuelve el recuento.Por ejemplo:

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

Esto supone que puede realizar el manejo de errores en el público. doIt método, ya que el count La variable en realidad no se devuelve a la persona que llama.Si necesita hacer eso, por supuesto podría lanzar una excepción:

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

Es difícil saber si eso ayudará sin saber más sobre cómo funciona realmente su algoritmo.