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

Question

Можно ли сохранить информацию через вспомогательную функцию с помощью java без использования статических переменных.

Например,

public void foo(){ 
    int v = 0; 
    fooHelper(2); 
} 

public void fooHelper(int depth){ 
    v++; 
    fooHelper(depth-1) 
} 

А именно я хочу обновить переменную V без потери информации для каждого рекурсивного случае, не имея доступа к переменной вне функции.

Answer 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().

Answer 2

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

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

Например:

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

Answer 3

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

Answer 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(); 
    } 
} 

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

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

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

Answer 7

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

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

Answer 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 для указания тонкой разницы между запоминанием и записью.