¿Refactorizar este método recursivo?

Question

Soy bastante nuevo en la idea de recursión y este es en realidad mi primer intento de escribir un método recursivo.

Traté de implementar una función recursiva Máx. Que pasa una matriz, junto con una variable que contiene el tamaño de la matriz para imprimir el elemento más grande.

Funciona, pero simplemente no siente ¡derecho!

También he notado que me parece que utilizar el modificador static mucho más que mis compañeros de clase en general ...

Puede alguien por favor proporcione algún consejo general, así como retroalimentación en cuanto a cómo puedo mejorar mi código?

public class RecursiveTry{ 

static int[] n = new int[] {1,2,4,3,3,32,100}; 
static int current = 0; 
static int maxValue = 0; 
static int SIZE = n.length; 

public static void main(String[] args){ 
    System.out.println(Max(n, SIZE)); 
} 

public static int Max(int[] n, int SIZE) { 
    if(current <= SIZE - 1){ 
     if (maxValue <= n[current]) { 
      maxValue = n[current]; 
      current++; 
      Max(n, SIZE);      
     } 
     else { 
      current++; 
      Max(n, SIZE); 
     } 
    } 
    return maxValue; 
} 

}

función

Answer 1

Su uso de variables estáticas para mantener el estado fuera de la función será una fuente de dificultad.

Un ejemplo de una implementación recursiva de un máximo() en pseudocódigo podría ser:

function Max(data, size) { 
    assert(size > 0) 
    if (size == 1) { 
     return data[0] 
    } 
    maxtail = Max(data[1..size], size-1) 
    if (data[0] > maxtail) { 
     return data[0] 
    } else { 
     return maxtail 
    } 
} 

La clave aquí es la llamada recursiva a Max(), donde se pasa todo excepto el primer elemento y uno menos que el tamaño. La idea general es que esta función dice "el valor máximo en estos datos es el primer elemento o el máximo de los valores en el resto de la matriz, el que sea mayor".

Esta implementación no requiere datos estáticos fuera de la definición de la función.

Una de las características de las implementaciones recursivas es una llamada "condición de terminación" que evita que la recursión continúe para siempre (o hasta que se produzca un desbordamiento de la pila). En el caso anterior, la prueba para size == 1 es la condición de terminación.

Answer 2

A "max" es el tipo equivocado de lo que escribir una función recursiva para - y el hecho de que está utilizando valores estáticos para "actual" y "maxValue" hace que su la función no es realmente una función recursiva.

¿Por qué no hacer algo un poco más susceptible a un algoritmo recursivo, como factorial?

Answer 3

Primero, ocupémonos del problema del alcance estático ... Su clase define un objeto, pero nunca crea una instancia. Desde principal está en el ámbito de forma estática, lo primero que debe hacer es conseguir un objeto, a continuación, ejecutar es métodos como éste:

public class RecursiveTry{ 

    private int[] n = {1,2,4,3,3,32,100}; 

    public static void main(String[] args){ 
     RecursiveTry maxObject = new RecursiveTry(); 
     System.out.println(maxObject.Max(maxObject.n, 0)); 
    } 

    public int Max(int[] n, int start) { 
     if(start == n.length - 1) { 
      return n[start]; 
     } else { 
      int maxRest = Max(n, start + 1); 
      if(n[start] > maxRest) { 
       return n[start]; 
      } 
      return maxRest; 
     } 
    } 

} 

Así que ahora tenemos un objeto llamado RecursiveTry maxObject que no requiere el alcance estático. No estoy seguro de que encontrar un máximo sea efectivo usando la recursión ya que el número de iteraciones en el método tradicional de bucle es más o menos equivalente, pero la cantidad de pila utilizada es mayor usando recursividad. Pero para este ejemplo, lo reduciría mucho.

Una de las ventajas de la recursión es que generalmente no es necesario que persista su estado durante las pruebas repetidas, como ocurre en la iteración. Aquí, he admitido el uso de una variable para mantener el punto de partida, porque consume menos CPU que pasando un nuevo int [] que contiene todos los elementos excepto el primero.

Answer 4

Básicamente está escribiendo una versión iterativa pero utilizando la recursividad de cola para el bucle. Además, al hacer que muchas variables estén estáticas, básicamente está utilizando variables globales en lugar de objetos. Aquí hay un intento de algo más cercano a una implementación recursiva típica. Por supuesto, en la vida real si usaba un lenguaje como Java que no optimiza las llamadas finales, implementaría una función "Máx" utilizando un bucle.

public class RecursiveTry{ 
    static int[] n; 

    public static void main(String[] args){ 
     RecursiveTry t = new RecursiveTry(new int[] {1,2,4,3,3,32,100}); 
     System.out.println(t.Max()); 
    }  

    RecursiveTry(int[] arg) { 
    n = arg; 
    } 

    public int Max() { 
    return MaxHelper(0); 
    } 

    private int MaxHelper(int index) { 
    if(index == n.length-1) { 
     return n[index]; 
    } else { 
     int maxrest = MaxHelper(index+1); 
     int current = n[index]; 
     if(current > maxrest) 
     return current; 
     else 
     return maxrest; 
    } 
    } 
} 

Answer 5

"not-homework"?

De todos modos. Lo primero es lo primero. El

static int[] n = new int[] {1,2,4,3,3,32,100}; 
static int SIZE = n.length; 

no tienen nada que ver con los parámetros de Max() con los que comparten sus nombres. Mueva estos a main y pierda los especificadores "estáticos". Se usan solo una vez, cuando se llama a la primera instancia de Max() desde adentro de main(). Su alcance no debe extenderse más allá de main().

No hay motivo para que todas las invocaciones de Max() compartan un solo índice "actual". "actual" debe ser local a Max(). Pero, entonces, ¿cómo podrían las recursiones sucesivas de Max() saber qué valor de "actual" usar? (Sugerencia: Max() ya está pasando otro Max() más abajo en la línea de algunos datos. Agregue "actual" a estos datos.)

Lo mismo ocurre con maxValue, aunque la situación aquí es un poco más complejo. No solo necesita pasar un "maxValue" actual por la línea, sino que cuando la recursión finaliza, debe volver a pasarla hasta la primera función Max(), que la devolverá a main(). Es posible que necesite ver otros ejemplos de recursión y pasar algún tiempo con este.

Finalmente, Max() en sí mismo es estático. Una vez que haya eliminado la necesidad de referirse a datos externos (las variables estáticas) sin embargo; realmente no importa. Simplemente significa que puede llamar a Max() sin tener que crear una instancia de un objeto.

Answer 6

Hacer que su función dependa de variables estáticas no es una buena idea. Aquí es posible implementación de recursiva función Max:

int Max(int[] array, int currentPos, int maxValue) { 
    // Ouch! 
    if (currentPos < 0) { 
     raise some error 
    } 
    // We reached the end of the array, return latest maxValue 
    if (currentPos >= array.length) { 
     return maxValue; 
    } 
    // Is current value greater then latest maxValue ? 
    int currentValue = array[currentPos]; 
    if (currentValue > maxValue) { 
     // currentValue is a new maxValue 
     return Max(array, currentPos + 1, currentValue); 
    } else { 
     // maxValue is still a max value 
     return Max(array, currentPos + 1, maxValue); 
    } 
} 
... 

int[] array = new int[] {...}; 
int currentPos = 0; 
int maxValue = array[currentPos] or minimum int value; 
    maxValue = Max(array, currentPos, maxValue); 

Answer 7

Como otros han observado, no hay necesidad de recursividad para implementar una función Max, pero puede ser instructivo para usar un algoritmo familiar para experimentar con una nueva concepto. Entonces, aquí está el código simplificado, con una explicación a continuación:

public class RecursiveTry 
{ 
    public static void main(String[] args) 
    { 
     System.out.println(Max(new int[] {1,2,4,3,3,32,100}, 0, 0)); 
    } 

    public static int Max(int[] n, int current, int maxValue) 
    { 
     if(current < n.Length) 
     { 
      if (maxValue <= n[current] || current == 0)) 
      { 
       return Max(n, current+1, n[current]); 
      } 
      return Max(n, current+1, maxValue); 
     } 
     return maxValue; 
    } 
} 

todo el estado estático no es necesario; en su lugar, todo se pasa en la pila. la lógica interna de la función Max se simplifica, y recurrimos de dos formas diferentes solo por diversión

Answer 8

De hecho, está sobreutilizando estática. En realidad, tampoco necesitas tantas variables globales. Intente mover

static int [] n = new int [] {1,2,4,3,3,32,100}; estática int current = 0; static int maxValue = 0; estático int TAMAÑO = n.length;

en la función main() para que sean variables locales.

public static void main(String[] args) 
{ 
    int[] n = new int[] {1,2,4,3,3,32,100}; 
    int current = 0; 
    int maxValue = 0; 
    int SIZE = n.length; 
    ...other code 

} 

No

una solución a su pregunta principal, pero su buena práctica utilizar las variables locales sobre las globales (en general)

--- Mientras termino esto, me doy cuenta de que estoy de accionamiento AIB lo dicho anteriormente

Answer 9

En el esquema anterior puede escribirse de manera muy concisa:

(define (max l) 
    (if (= (length l) 1) 
     (first l) 
     (local ([define maxRest (max (rest l))]) 
      (if (> (first l) maxRest) 
       (first l) 
       maxRest)))) 

Por supuesto, esto usa listas enlazadas y no matrices, por lo que no pasé un ele tamaño miento, pero siento que esto destila el problema hasta su esencia. Esta es la definición del pseudocódigo:

define max of a list as: 
    if the list has one element, return that element 
    otherwise, the max of the list will be the max between the first element and the max of the rest of the list 

Answer 10

Aquí hay una versión de Java para usted.

public class Recursion { 

    public static void main(String[] args) { 
     int[] data = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 
     System.out.println("Max: " + max(0, data)); 
    } 

    public static int max(int i, int[] arr) { 
     if(i == arr.length-1) { 
      return arr[i]; 
     } 

     int memo = max(i+1, arr); 
     if(arr[i] > memo) { 
      return arr[i]; 
     } 
     return memo; 
    } 
} 

relación La recurrencia es que el elemento máximo de una matriz es o bien el primer elemento, o el máximo del resto de la matriz. La condición de detención se alcanza cuando llega al final de la matriz. Tenga en cuenta el uso de la memorización para reducir las llamadas recursivas (aproximadamente) a la mitad.

Answer 11

Una manera más agradable de obtener el valor máximo de una matriz recursivamente sería implementar quicksort (que es un buen algoritmo de ordenación recursivo), y luego simplemente devolver el primer valor.

Aquí hay algunos Java code for quicksort.

Answer 12

codesize más pequeño que pude conseguir:

public class RecursiveTry { 
    public static void main(String[] args) { 
     int[] x = new int[] {1,2,4,3,3,32,100}; 
     System.out.println(Max(x, 0)); 
    } 

    public static int Max(int[] arr, int currPos) { 
     if (arr.length == 0) return -1; 
     if (currPos == arr.length) return arr[0]; 
     int len = Max (arr, currPos + 1); 
     if (len < arr[currPos]) return arr[currPos]; 
     return len; 
    } 
} 

algunas cosas:

1/Si la matriz es cero tamaño, se devuelve un máximo de -1 (que podría tener otro valor del marcador, decir, -MAX_INT, o lanzar una excepción). Aquí asumí la suposición de la claridad del código para asumir que todos los valores son cero o más. De lo contrario, habría salpicado el código con todo tipo de cosas innecesarias (en lo que respecta a responder a la pregunta).

2/La mayoría de las recurrencias son 'más limpias' en mi opinión si el caso de terminación es no-data en lugar de last-data, por lo tanto devuelvo un valor garantizado menor o igual al máximo cuando terminamos el formación. Otros pueden diferir en su opinión, pero no sería la primera ni la última vez que se equivocaron :-).

3/La llamada recursiva obtiene el máximo del resto de la lista y la compara con el elemento actual, devolviendo el máximo de los dos.

4/La solución 'ideal' hubiera sido pasar una matriz modificada en cada llamada recursiva para que solo comparase el primer elemento con el resto de la lista, eliminando la necesidad de currPos. Pero eso habría sido ineficiente y habría reducido la ira de SO.

5/Esta puede no ser necesariamente la mejor solución. Puede ser que la materia gris se haya visto comprometida por el uso excesivo de LISP con su CAR, CDR y esos paréntesis interminables.