Как сохранить счет «все сделано» в рекурсивном алгоритме в Java?

Question

У меня есть рекурсивный алгоритм, который просматривает строку, символ за символом, и анализирует его, чтобы создать древовидную структуру. Я хочу иметь возможность отслеживать индекс символа, в котором в данный момент находится анализатор (для сообщений об ошибках, как и все остальное), но я не заинтересован в реализации чего-либо вроде кортежа для обработки нескольких возвращаемых типов.

Я попытался использовать тип Integer, объявленный вне метода и переданный в рекурсивный метод, но поскольку он является окончательным, приращения рекурсивного вызова «забыты»; когда я вернусь. (Поскольку приращение значения Integer делает эталонную точку переданного по значению объекта новым объектом)

Есть ли способ получить что-то похожее на работу, которая не будет загрязнять мой код?

Answer 1

Поскольку вы уже обнаружили псевдо-изменяемое целое число " hack, " как насчет этого варианта:

Имеет ли смысл создавать отдельный класс Parser? Если вы сделаете это, вы можете сохранить текущее состояние в переменной-члене. Возможно, вам нужно подумать о том, как вы собираетесь решать любые проблемы безопасности потоков, и это может быть излишним для этого конкретного приложения, но это может сработать для вас.

Answer 2

Это что-то вроде хака, но иногда я использую AtomicInteger, который является изменяемым, чтобы делать такие вещи. Я также видел случаи, когда передается int [] размера 1.

Answer 3

Текущее решение, которое я использую:

int[] counter = {0};

и затем передайте его рекурсивному алгоритму:

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

и когда я хочу увеличить его:

counter[0]++;

Не супер элегантно, но работает ...

Answer 4

Целые числа являются неизменяемыми, что означает, что когда вы передаете его в качестве аргумента, он создает копию, а не ссылку на тот же элемент. ( объяснение ).

Чтобы получить поведение, которое вы ищете, вы можете написать свой собственный класс, который похож на Integer только изменяемый. Затем просто передайте его в рекурсивную функцию, он увеличивается в пределах рекурсии, и при повторном доступе к нему после завершения рекурсии он все равно сохранит свои новые значения.

Редактировать. Обратите внимание, что использование массива int [] является разновидностью этого метода ... В Java массивы также передаются по ссылке, а не копируются как примитивы или неизменные классы.

Answer 5

Вы можете просто использовать статическую переменную класса int, которая увеличивается при каждом вызове метода doIt.

Answer 6

Вы также можете сделать:

private int recurse (int i) {

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

    return i;
}

Answer 7

Если честно, я бы перекодировал функцию, чтобы сделать ее линейным алгоритмом, использующим цикл. Таким образом, у вас нет шансов исчерпать пространство кучи, если вы шагаете через чрезвычайно большую строку. Кроме того, вам не нужно иметь дополнительный параметр, чтобы отслеживать количество.

Вероятно, это также приведет к ускорению алгоритма, поскольку не нужно вызывать функцию для каждого символа.

Если, конечно, нет конкретной причины, она должна быть рекурсивной.

Answer 8

Одна из возможностей, которую я могу придумать, - сохранить счетчик в переменной-члене класса. Это, конечно, предполагает, что открытый метод doIt вызывается только одним потоком.

Другой вариант - это реорганизовать открытый метод для вызова частного вспомогательного метода. Закрытый метод принимает список в качестве параметра и возвращает количество. Например:

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

Предполагается, что вы можете выполнять обработку ошибок в общедоступном методе doIt , поскольку переменная count фактически не передается вызывающей стороне. Если вам нужно сделать это, вы, конечно, можете выдать исключение:

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

Трудно понять, поможет ли это, не зная больше о том, как на самом деле работает ваш алгоритм.