Java сохраняет информацию в рекурсивной функции

Ответ 1

Забудьте обо всех ответах, которые говорят вам объявлять атрибуты, или обновлять изменяемые объекты в каждом рекурсивном вызове. В истинном функциональном рекурсивном стиле вы "сохраняете" информацию, передавая ее как параметры и/или возвращаемые типы.

Позвольте мне проиллюстрировать простым примером, скажем, что вы хотите рекурсивно вычислить сумму элементов в int[]. Здесь состояние (информация, которая должна быть сохранена между рекурсивными вызовами), является текущим индексом в массиве и суммой. Вот как это сделать:

public int sum(int[] array) {
    return sum(array, 0, 0); 
}

private int sum(int[] array, int idx, int acc) {
    if (idx == array.length)
        return acc;
    return sum(array, idx+1, acc+array[idx]);
}

Назовите его следующим образом:

int[] array = {1, 2, 3};
System.out.println(sum(array));

Как вы можете видеть, нет необходимости объявлять (статические или экземпляры) атрибуты и не нужно передавать и изменять изменяемые объекты (списки, карты) - я даже не использую локальные переменные, потому что требуется вся необходимая информация для решения проблемы присутствует как параметр метода.

В коде вашего вопроса переменная v должна выполнять то, что в моем ответе выполняет параметр acc, а именно: изменение накопленного значения каждый раз, когда вызывается рекурсия. В конце вам просто нужно вернуть накопленное значение из вспомогательной функции (которая не должна иметь тип возврата void) и что вы получите значение в foo().

Ответ 2

Переменная, объявленная в области (например, метод), доступна только в этой области (например, не в другом методе).

Если информация важна только для метода, сохраните переменную в методе. Если информация актуальна для всего состояния объекта/класса, сохраните ее как элемент класса (статический/нестатический).

Например:

public void someRecursiveMethod(int num) {
    while (num < 10) {
        num++;
        someRecursiveMethod(num);
        System.out.println("Current num = " + num);
    }
}

Ответ 3

Вы можете создать новый класс (yuck) или передать переменную в качестве параметра и вернуть ее в fooHelper.

Ответ 4

Почему бы не сделать его переменной экземпляра (не обязательно статическим)...??

public class Recursive {
    int v = 0;
    public void foo(){

        fooHelper(2);
        System.out.println(v);
    }

    public void fooHelper(int depth){
        v++;
        if(depth-1!=0)//Added this because I was getting an StackOverflowError
        fooHelper(depth-1);
    }

    public static void main(String[] args) {
        Recursive r = new Recursive();
        r.foo();
    }
}

Ответ 5

Вы можете вернуть список или аналогичную структуру данных:

public List<Integer> fooHelper( int v, int depth ){
    if( depth == 0 ) return new ArrayList();

    v++;
    List<Integer> result = fooHelper( v, depth-1 );

    result.add( new Integer(v) );

    return result;
}

Ответ 6

Поскольку переменная v имеет примитивный тип, внесенные в нее изменения не будут видны вне области функции. Вы можете объявить переменную v внутри класса, например State и передать объект состояния в рекурсивную функцию, чтобы получить требуемый эффект.

public void foo(){
    State state = new State();
    fooHelper(state, 2);
}

public void fooHelper(State state, int depth){
    state.v++;
    fooHelper(state, depth-1);
}

class State {
    int v;
}

Надеюсь, что это поможет.

Ответ 7

Вы можете передать объект для хранения обновления для каждого рекурсивного вызова. Что-то вроде ниже.

public static void fooHelper(int depth, HashMap map){
      map.put(depth, "Call " + depth);
      if (depth > 0)
      {
        fooHelper(depth-1, map);
      }
      return;
    }

Ответ 8

Я думаю, это называется memoization. Он выглядит как

class Fibonacci
{
     public Map < Integer , Integer > memorized = new HashMap < > ( ) ;

     public int fib ( int n )
     {
           if ( memoized . containsKey ( n ) )
           {
                 return memoized . get ( n ) ;
           }
           else
           {
                 int fib = // calculate recursively
                 memoized . put ( n , fib ) ;
                 return fib ;
           }
     }
}

Вы должны иметь возможность получить достойную (не оптимальную) производительность из этого алгоритма. Основная причина, по которой алгоритм рекурсивного фибоначчи имеет ужасную производительность, - это b/c, он многократно вычисляет одни и те же значения. С рекурсией + memoization он никогда не вычисляет какое-либо значение более одного раза.

Благодаря @Aristide для указания тонкой разницы между запоминанием и записью.

Ответ 9

[Можно ли задать соответствующий уточняющий вопрос?]

Я понимаю, как считать вверх или вниз: recurse (myString, count + 1); recurse (myString, count-1);

Но какой самый простой способ повторить достижение некоторого базового случая, инициировать его достижение и сообщить кадрам нижнего стека, что достигнут "успех" - что они могут выполнить свою дополнительную работу после возвращения, если я возвращаюсь Строка, и не может вернуть логическое значение?

У меня такое чувство, что я могу: передать булев объект, на который каждый кадр ссылается. Передайте пользовательский объект-оболочку.

Я просто хотел бы лучшие практики...

В моем случае я хочу вернуть k-го предка искомого узла. Медленный бегун, k узлов обратно в стек рекурсии, должен услышать: "найдено!", Чтобы он мог вернуть узел.

Спасибо! (Если мне нужно переместить это, я попытаюсь.)