¿Cuál es más rápido en Java, mientras que o usando un método recursivo?

loops recursion

Question

Tengo la siguiente class muestra con estos dos métodos:

Process.java:

public class Process {

    public Process() {
    }

    public static void countRecursive(int num) {
        System.out.println("countRecursive: " + num++);
        if (num <= 10) countRecursive(num);
        else return;
    }

    public static void countWhile(int num) {
        do System.out.println("countWhile: " + num++);
        while (num <= 10);
    }

}

Clase principal:

public static void main(String[] args) {        

    Process.countRecursive(0);
    Process.countWhile(0);

}

Salida:

countRecursive: 0
countRecursive: 1
countRecursive: 2
countRecursive: 3
countRecursive: 4
countRecursive: 5
countRecursive: 6
countRecursive: 7
countRecursive: 8
countRecursive: 9
countRecursive: 10

countWhile: 0
countWhile: 1
countWhile: 2
countWhile: 3
countWhile: 4
countWhile: 5
countWhile: 6
countWhile: 7
countWhile: 8
countWhile: 9
countWhile: 10

Pero quiero saber qué "técnica" se recomienda usar y por qué.

Gracias por adelantado.

Answer 1

Debe ejecutar el código con la medición del tiempo. Aquí tienes mi salida para 100 recursiones / 100 mientras bucles:

Recursive time: 90941
While time: 5180

Esto muestra claramente que mientras que el bucle es más rápido que la recursión.

Puedes verificar mis medidas ejecutando este código:

public class Process {

    public Process() {
    }

    public static void countRecursive(int num) {
        num++;
        if (num <= 100) countRecursive(num);
        else return;
    }

    public static void countWhile(int num) {
        do
            num++;
        while (num <= 100);
    }

    public static void main(String[] args) {
        Long start = System.nanoTime();        
        Process.countRecursive(0);
        System.out.println("Recursive time: " + (System.nanoTime() - start));
        Long startWhile = System.nanoTime();
        Process.countWhile(0);
        System.out.println("While time: " + (System.nanoTime() - startWhile));

    }

}

Answer 2

En general, la recursión está optimizada para los bucles si es posible, lo que significa que, por diversas razones, incluyendo la asignación de tramas de pila y los desbordamientos de tramas de pila, la iteración es favorable sobre la recursión si las dos soluciones son iguales. Ver Recursión de cola
Por lo tanto, ignorando el hecho de que Java no optimiza la recursión de cola, los bucles deberían ser más rápidos.

También eche un vistazo a this

Answer 3

En general, prefiero la iteración (por ejemplo, un tiempo o para un bucle) sobre la recursión porque:

• La iteración es más simple
• Si recibe una respuesta demasiado profunda, puede obtener una excepción de . Esto no puede suceder con la iteración.

Answer 4

En java, la recursión es poco costosa en comparación con el bucle while porque requiere la asignación de un nuevo marco de pila. La recursión puede ser más rápida donde la alternativa es administrar explícitamente una pila

Answer 5

La recursión será más lenta debido a la sobrecarga de llamadas al método y al uso de la pila de llamadas.

Java tampoco está realizando la optimización de llamadas de cola, así que no cuentes con ello. (Aunque hay idiomas en la JVM que tienen optimización de llamadas de cola, incluidos Clojure y Kotlin)

Otro inconveniente podría ser el riesgo de un Error en caso de que esté llenando la pila.

Si está haciendo esto solo para probar cosas, sugiero usar VisualVM, que se puede encontrar en el JDK de Java. Es un perfilador que puede utilizarse para evaluar este tipo de situaciones.

Por favor, tenga en cuenta que no recomiendo usar la recursividad solo para ser elegante. Úselo si realmente lo necesita (por ejemplo, atravesar árboles).

Answer 6

Las llamadas recursivas agregan marcos de pila a la pila de llamadas. Loops no lo hacen. Los bucles son generalmente más rápidos que la recursión, a menos que la recursión sea parte de un algoritmo como dividir y conquistar (que su ejemplo no lo es).

Debería poder cronometrar la ejecución de cada uno de sus métodos y descubrir cuánto más rápido es uno que el otro.

Answer 7

Lo que todos los demás dijeron es verdad. Me gustaría agregar una cosa más: para el problema que publicaste, contar de 1 a 10, usar la recursión o la iteración estará bien de cualquier manera, ya que ambos toman una cantidad de tiempo despreciable para ejecutarse. En general, en los sistemas informáticos modernos, no tiene que preocuparse demasiado por el tiempo que tardará en completarse un proceso (a menos que se trate de grandes conjuntos de datos) porque la memoria es muy barata y las CPU son muy potentes.

Por lo general, usted escribe un programa, pero primero se siente más cómodo utilizando buenas prácticas de programación. Si demora demasiado en ejecutarse después de eso, entonces lo optimizas.

No es una mala cosa mirar cómo se comparan la iteración y la recursión en este nivel. De nuevo, la iteración suele ser preferible a la recursión. Mi punto es que la lección que hay que aprender es que, si bien hay formas de hacer que su código se ejecute rápidamente, a menudo no tiene que preocuparse por ellos cuando trabaja con conjuntos de datos pequeños :)

Answer 8

No sugeriría usar Recursión, ya que cada recursión se almacena en la pila. Por lo tanto, debe almacenar los parámetros del método, las variables locales, etc., para cada llamada recursiva, para mantener el estado del método antes de esa llamada.

Además, es obvio que no debe recurrir a este tipo de problema. Debe dejarse para una tarea específica, solo cuando realmente no puede evitar usarlos.

Además, también puedes comparar tu código para ver cuál se ejecuta más rápido. Tendrás una idea.