Decidí implementar un programa muy simple de forma recursiva, para ver qué tan bien Java maneja la recursividad*, y se acercó un poco corto. Esto es lo que terminé de escribir:

public class largestInIntArray {
  public static void main(String[] args)
  {
    //These three lines just set up an array of ints:
    int[] ints = new int[100];
    java.util.Random r = new java.util.Random();
    for(int i = 0; i < 100; i++) ints[i] = r.nextInt();

    System.out.print("Normal:"+normal(ints,-1)+" Recursive:"+recursive(ints,-1));
  }

  private static int normal(int[] input, int largest) {
    for(int i : input)
      if(i > largest) largest = i;

    return largest;
  }

  private static int recursive(int[] ints, int largest) {
    if(ints.length == 1)
      return ints[0] > largest ? ints[0] : largest;

    int[] newints = new int[ints.length - 1];
    System.arraycopy(ints, 1, newints, 0, ints.length - 1); 

    return recursive(newints, ints[0] > largest ? ints[0] : largest);
  }
}

Y que funciona bien, pero como es un poco feo que me preguntaba si había una manera mejor. Si alguien tiene alguna idea/alternativas/azúcar sintáctico para compartir, que sería muy apreciada!

P. s. Si usted dice «el uso de Lisp» a veces se gana nada (pero con respeto). Quiero saber si esto puede ser hecho para parecer agradable en Java.

*y lo bien que me manejar la recursividad

La recursividad es que no va a ser tan simple o eficiente en Java como iteración, excepto casos muy raros.
Sí, pero si alguien va a estar bien preparados para el espacio de la complejidad de la recursividad, es un desarrollador de Java 🙂
En cualquier idioma, siempre tendrás que copiar la matriz, o pasar índices en la matriz. Si te refieres a «Lisp utilizando una lista enlazada», entonces seguro, es más agradable que el «Java utilizando una matriz», pero creo que «X utilizando una lista enlazada» es mejor que «Y el uso de una matriz» para cualquier X e Y. (Desplazados matrices en Common Lisp manejar un poco de la contabilidad para usted, pero no creo que ellos realmente hacen de este caso mucho más simple.)

OriginalEl autor Robert Grant | 2009-12-31

11 Comentarios

  1. 7

    2 mejoras:

    • que no hay ninguna copia de la matriz (sólo mediante el desplazamiento)
    • no hay necesidad de dar la máxima

      private static int recursive(int[] ints, int offset) {
          if (ints.length - 1 == offset) {
              return ints[offset];
          } else {
              return Math.max(ints[offset], recursive(ints, offset + 1));
          }
      }

    Inicio de la recursividad con recursive(ints, 0).

    Yo en realidad prefiere ésta debido a su uso de la recursividad es más legant que la respuesta ganadora, pero no hacer algunas cosas de el ganador. Gracias 🙂
    Como? La única diferencia a mis ojos, es el manejo de un array vacío que produce una excepción aquí (bueno, no hay ninguna max así que no hay buena respuesta) vs regresar a un arbitrario (false) valor de la respuesta ganadora.
    Buen punto. Cambió.

    OriginalEl autor Jerome

  2. 10

    He aquí cómo yo podría hacer el método recursivo más bonito:

      private static int recursive(int[] ints, int largest, int start) {
        if (start == ints.length) {
          return largest;
        }
        return recursive(ints, Math.max(ints[start], largest), start + 1);
      }

    De este modo evita que las caras de la matriz de copia, y las obras de un vacío de la matriz de entrada. Usted puede implementar un adicional de método sobrecargado con sólo dos parámetros para la misma firma que el proceso iterativo de la función:

      private static int recursive(int[] ints, int largest) {
        return recursive(ints, largest, 0);
      }
    JOOI, ¿hay alguna diferencia entre las Matemáticas.max, y un operador ternario con un superior?
    Sí, me parece que el uso max() es más fácil de leer que el uso de Java operador condicional para el mismo propósito. Si hay una diferencia de rendimiento, tendría que medir para su entorno específico.
    Con max (a) usted no tiene que Repetir a Ti mismo.

    OriginalEl autor Greg Hewgill

  3. 2

    Podría pasar el índice actual como un parámetro en lugar de copiar casi la totalidad de la matriz de cada tiempo o usted puede utilizar un divide y vencerás enfoque.

    OriginalEl autor ggf31416

  4. 1
    public static int max(int[] numbers) {
      int size = numbers.length;
      return max(numbers, size-1, numbers[size-1]);
    }
    
    public static int max(int[] numbers, int index, int largest) {
      largest = Math.max(largest, numbers[index]);
      return index > 0 ? max(numbers, index-1, largest) : largest;
    }

    OriginalEl autor cletus

  5. 1

    … a ver cómo Java maneja la recursividad

    La respuesta simple es que Java no soporta la recursividad. Específicamente, el Sol y los compiladores de java Jvm Hotspot no aplicar la cola de llamadas recursividad de optimización, por lo que la recursividad intensivo de algoritmos puede fácilmente consumir una gran cantidad de espacio en la pila.

    Sin embargo, he visto artículos que decir que IBM Jvm hacer apoyo de esta optimización. Y vi a un correo electrónico de algunos no-Sol hombre que le dijo que era su adición como una experimentales Hotspot extensión como un proyecto de tesis.

    Me pregunto si fue algo que salió de esta.
    al Parecer, nada 🙂

    OriginalEl autor Stephen C

  6. 1

    Aquí está una leve variación, mostrando cómo las Listas Enlazadas son a menudo un poco más agradable para la recursividad, donde «mejor» significa «menos de parámetros en la firma del método»

      private static int recursive(LinkedList<Integer> list) {
        if (list.size() == 1){
          return list.removeFirst();
        }
        return Math.max(list.removeFirst(),recursive(list));
      }

    OriginalEl autor Peter Recore

  7. 0

    Su código recurrente utiliza System.arrayCopy, pero su iterativo código de no hacerlo, de manera que su microbenchmark no va a ser exacta. Como otros han mencionado, usted puede limpiar hasta que el código mediante Math.min y el uso de un índice de la matriz en lugar de la cola, como en el enfoque que tenía.

    OriginalEl autor Kristopher Ives

  8. 0
    public class Maximum 
    {
    
        /**
         * Just adapted the iterative approach of finding maximum and formed a recursive function
         */
        public static int max(int[] arr,int n,int m)
        {
            if(m < arr[n])
            {
                m = arr[n];
                return max(arr,n - 1,m);
            }
            return m;
        }
        public static void main(String[] args) 
        {
           int[] arr = {1,2,3,4,5,10,203,2,244,245,1000,55000,2223};
           int max1 =  max(arr,arr.length-1,arr[0]);
           System.out.println("Max: "+ max1);
        }
    }
    Bienvenido a Desbordamiento de Pila! Habría que considerar la adición de cierta narrativa para explicar el porqué de este código funciona, y lo que hace que sea una respuesta a la pregunta? Esto sería muy útil para la persona que hace la pregunta, y cualquier otra persona que viene junto.

    OriginalEl autor Kalel314

  9. 0

    De hecho tengo una pre hechas de clase que tengo que instalar para encontrar el entero más grande de cualquier conjunto de valores. Usted puede poner la clase en el proyecto y simplemente usar en cualquier clase así:

     System.out.println(figures.getLargest(8,6,12,9,120));

    Se devuelve el valor de «120» y colocarlo en la salida. Aquí es el de los métodos de código fuente si usted está interesado en el uso de:

    public class figures {
    
    public static int getLargest(int...f) {
       int[] score = new int[f.length];
        int largest=0;
        for(int x=0;x<f.length;x++) {
            for(int z=0;z<f.length;z++) {
                if(f[x]>=f[z]) {
                    score[x]++;
                }else if(f[x]<f[z]) {
    
                }else {
                    continue;
                }
                if(z>=f.length) {
                    z=0;
                    break;
                }
            }
        }
        for(int fg=0;fg<f.length;fg++) {
            if(score[fg]==f.length) {
                largest = f[fg];
            }
        }
        return largest;
        }
    }

    OriginalEl autor JeremyF

  10. 0

    El siguiente es un ejemplo de código dado por mi Java instructor, Profesor Penn Wu, en una de sus conferencias. Espero que ayude.

    importar java.util.Al azar;

    clase pública Recursividad
    {
    static int s = 0;

    public static Double max(Double[] d, int n, Double max)
    {
    if (n==0) { return max;}
    otra cosa
    {

    si (d[n] > máx.)
    {
    max = d[n];
    }

    volver max(d, n-1, max);

    }
    }

    public static void main(String[] args)
    {
    Al azar rn = new Random();
    Double[] d = new Double[15];

    for (int i=0; i {
    d[i] = rn.nextDouble();
    Sistema..println(d[i]);
    }

    Sistema..print("\nMax: "+ max(d, d.longitud-1, d[0]));
    }
    }
    Bienvenido a! Por favor, considere la posibilidad de editar tu pregunta para incluir explicaciones detalladas de por qué y cómo este código responde a la pregunta. Además, puede que desee recibir un permiso antes de publicar un profesor en el código o su nombre asociado con dicho código, así como una cortesía común.

    OriginalEl autor JavaStudent

  11. 0

    Aquí es mi alternativa

    public class recursion
    {
      public static int max( int[] n, int index )
      {
        if(index == n.length-1)   //If it's simple, solve it immediately:
          return n[index];        //when there's only one number, return it
        if(max(n, index+1) > n [index]) //is one number bigger than n?
          return max(n, index+1); //return the rest, which contains that bigger number
        return n[index];          //if not, return n which must be the biggest number then
      }
    
      public static void main(String[] args)
      {
        int[] n = {100, 3, 5, 1, 2, 10, 2, 15, -1, 20, -1203}; //just some numbers for testing
        System.out.println(max(n,0));
      }
    }

    OriginalEl autor Tschaeggaer

Dejar respuesta

Please enter your comment!
Please enter your name here