Como manter uma contagem de “coisas feitas” em um algoritmo recursivo em Java?

Question

Eu tenho um algoritmo recursivo que percorre uma string, caractere por caractere, e a analisa para criar uma estrutura semelhante a uma árvore.Quero ser capaz de acompanhar o índice de caracteres em que o analisador está atualmente (tanto para mensagens de erro quanto para qualquer outra coisa), mas não estou interessado em implementar algo como uma tupla para lidar com vários tipos retornados.

Tentei usar um tipo Integer, declarado fora do método e passado para o método recursivo, mas por ser final, os incrementos de chamada recursiva são "esquecidos" quando eu retorno.(Porque o incremento do valor Inteiro faz com que a referência do objeto passado por valor aponte para um novo objeto)

Existe uma maneira de fazer algo semelhante funcionar que não polua meu código?

Answer 1

Como você já descobriu o "hack" de números inteiros pseudo-mutáveis, que tal esta opção:

Faz sentido criar uma classe Parser separada?Se você fizer isso, poderá armazenar o estado atual em uma variável de membro.Você provavelmente precisará pensar em como lidará com quaisquer problemas de segurança de thread, e isso pode ser um exagero para esse aplicativo específico, mas pode funcionar para você.

Answer 2

É meio que um hack, mas às vezes eu uso um AtomicInteger, que é mutável, para fazer coisas assim.Também vi casos em que um int[] de tamanho 1 é passado.

Answer 3

A solução atual que estou usando é:

int[] counter = {0};

e depois passe para o algoritmo recursivo:

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

e quando eu quiser incrementá-lo:

counter[0]++;

Não é super elegante, mas funciona...

Answer 4

Os números inteiros são imutáveis, o que significa que quando você os passa como argumento, eles criam uma cópia em vez de uma referência ao mesmo item.(explicação).

Para obter o comportamento que você está procurando, você pode escrever sua própria classe, que é mutável apenas como Inteiro.Depois, basta passá-lo para a função recursiva, ele é incrementado dentro da recursão, e quando você acessá-lo novamente após o término da recursão ele ainda manterá seus novos valores.

Editar:Observe que usar um array int[] é uma variação deste método...Em Java, os arrays também são passados ​​por referência, em vez de copiados como primitivos ou classes imutáveis.

Answer 5

Você poderia simplesmente usar uma variável de classe estática int que é incrementada cada vez que seu método doIt é chamado.

Answer 6

Você também pode fazer:

private int recurse (int i) {

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

    return i;
}

Answer 7

Para ser honesto, eu recodificaria a função para torná-la um algoritmo linear que usa um loop.Dessa forma, você não terá chance de ficar sem espaço no heap se estiver percorrendo uma string extremamente grande.Além disso, você não precisaria ter um parâmetro extra apenas para controlar a contagem.

Isso provavelmente também teria como resultado tornar o algoritmo mais rápido, porque ele não precisa fazer uma chamada de função para cada caractere.

A menos, é claro, que haja um motivo específico para que ele seja recursivo.

Answer 8

Uma possibilidade que consigo pensar é armazenar a contagem em uma variável membro da classe.Isto pressupõe, naturalmente, que o público doIt O método é chamado apenas por um único thread.

Outra opção é refatorar o método público para chamar um método auxiliar privado.O método privado toma a lista como parâmetro e retorna a contagem.Por exemplo:

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

Isso pressupõe que você pode fazer o tratamento de erros no público doIt método, uma vez que o count variável não é realmente passada de volta para o chamador.Se você precisar fazer isso, é claro que poderá lançar uma exceção:

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

É difícil saber se isso ajudará sem saber mais sobre como seu algoritmo realmente funciona.