java retener información en la función recursiva

Question

Es posible retener información a través de una función auxiliar con java, sin usar variables estáticas.

Por ejemplo,

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

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

A saber Quiero actualizar la variable v sin perder la información de cada caso recursivo, sin tener que acceder a una variable fuera de la función.

Answer 1

Olvídate de todas las respuestas que te dicen que declares atributos, o para actualizar objetos mutables en cada llamada recursiva. En un verdadero estilo funcional y recursivo, usted "conserva" la información pasándola como parámetros y/o tipos de devolución.

Déjenme ilustrar con un ejemplo simple, digamos que desea calcular recursivamente la suma de los elementos en un int[]. Aquí, el estado (la información que debe conservarse entre llamadas recursivas) es el índice actual en la matriz y la suma hasta el momento.He aquí cómo hacerlo:

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

llamada así:

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

Como se puede ver, no hay necesidad de declarar (estática o instancia) atributos, y no hay necesidad de aprobar y modificar mutable objetos (listas, mapas) - Ni siquiera estoy usando variables locales, porque toda la información requerida para resolver el problema está presente como parámetros del método.

En el código de su pregunta, se supone que la variable v hace lo que hace el parámetro acc en mi respuesta, a saber: modificar un valor acumulado cada vez que se invoca la recursión. Al final, solo necesita devolver el valor acumulado de la función auxiliar (que no debe tener un tipo de devolución void) y así obtendrá el valor en foo().

Answer 2

Una variable declarada en un ámbito (por ejemplo, el método) es accesible solo en este ámbito (por ejemplo, no en otro método).

Si la información es relevante solo para el método, mantenga la variable en el método. Si la información es relevante para todo el estado del objeto/clase, mantenlo como miembro de la clase (estático/no estático).

Por ejemplo:

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

Answer 3

Puede crear una nueva clase (puaj), o pasar la variable como un parámetro y devolverlo en fooHelper.

Answer 4

¿Por qué no hacer que sea una variable de instancia (no necesariamente estática) ... ??

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

Usted puede devolver una lista o una estructura de datos similar:

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

Debido a que la variable v es de tipo primitivo, los cambios realizados no serán visibles fuera del ámbito de la función. Puede declarar la variable v dentro de una clase, decir Estado y pasar el objeto de estado a la función recursiva para obtener el efecto requerido.

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

Espero que ayude.

Answer 7

Puede pasar un objeto para almacenar la actualización para cada llamada recursiva. Algo como el de abajo.

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

Answer 8

Creo que esto se llama memorización. Parece que

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

Debería poder obtener un rendimiento decente (no óptimo) con este algoritmo. La razón principal por la cual el algoritmo de fibonacci recursivo tiene un rendimiento horrible es porque está calculando repetidamente los mismos valores. Con la recursividad + memorización nunca se calcula ningún valor más de una vez.

Gracias a @Aristide por señalar la sutil diferencia entre la memorización y la memorización.