java - usar - recursividad programacion

¿Los métodos recursivos son siempre mejores que los métodos iterativos en Java?

Question

¿Los métodos recursivos son siempre mejores que los métodos iterativos en Java?

¿También pueden usarse siempre en lugar de iteración y viceversa?

Answer 1

¿Los métodos recursivos son siempre mejores que los métodos iterativos en java?

No

¿También pueden usarse siempre en lugar de iteración y viceversa?

Siempre se puede hacer que una función recursiva sea iterativa. (Si la memoria puede manejarlo, vea el enlace interesante here )

Para algunos casos, es mejor usar la recursión (como cuando se trata de árboles ... viajando en un árbol binario ... etc.). Para mí, si usar bucles no es más complicado y mucho más difícil que una recursión, prefiero usar bucles.

La recursión utiliza más memoria, pero a veces es más clara y más legible. El uso de bucles aumenta el rendimiento, pero la recursión a veces puede ser mejor para el programador (y su rendimiento).

Entonces, para concluir, decidir qué usar: recursión o iteración, depende de lo que quiera implementar, y lo que es más importante para usted (legibilidad, rendimiento ...) y pedir recursión o iteración es como pedir elegancia o rendimiento .

Ejemplo

Considere estas dos implementaciones para el factorial :

Iterativo:

private int Factorial(int num)
{
    int result = 1;
    if (num <= 1) 
       return result;
    while (num > 1)
    {
        result * = num;
        num--;
    }
    return result;
}

Recursion

private int Factorial(int num)
{
    if (num <= 1) 
        return 1;
    return num * Factorial(num - 1);
}

¿Qué método es más legible?

Obviamente, el recursivo, es sencillo y puede escribirse y ejecutarse con éxito desde el primer intento. ¡Es simplemente traducir la definición matemática a Java !

¿Qué método es más eficiente?

Tomemos por ejemplo num = 40 , aquí hay una comparación de tiempo :

long start = System.nanoTime();
int res = Factorial(40);
long end = System.nanoTime();
long elapsed = end - start;

System.out.println("Time: " + elapsed); 

2993 para el recursivo

2138 para el iterativo

por supuesto, la diferencia será mayor cuando num sea más grande ..

Answer 2

Corregir otras respuestas: cualquier iteración puede transformarse en recursión (con la advertencia de que puede ocurrir un desbordamiento de pila). Sin embargo , no todas las recursiones se pueden transformar directamente en iteración. A menudo, necesitará algún tipo de espacio de memoria virtual para almacenar los datos que de lo contrario se almacenarán en la pila.

En cuanto a cuál elegir: eso depende de su idioma y de la conveniencia de escribir una solución recursiva.

Editar, para aclarar lo que quiero decir con "directamente":

Hay tres tipos de recursión, según la forma en que se pueden convertir directamente a iteración:

• Tail-call optimizable, en el que la última operación en el método es la llamada recursiva. Estos se pueden traducir directamente en un bucle.
• Recursión que no es optimizable para llamadas de cola, porque requiere que la información se conserve entre las llamadas, pero no necesita una pila. Un factorial expresado como fact(N) es el ejemplo clásico: en una formulación recursiva, la última operación no es una llamada recursiva, sino una multiplicación. Estos tipos de llamadas recursivas se pueden transformar fácilmente en una forma optimizable de llamada de cola, y de allí en una forma iterativa (para transformar factorial en una forma optimizable de llamada de cola, debe usar un fact(n, acc) versión de dos argumentos fact(n, acc) , donde acc es el resultado acumulado).
• Recursión que requiere que se mantenga el estado en cada llamada. El ejemplo clásico es un recorrido de árbol de preorden: en cada llamada, debe recordar el nodo principal. No hay manera de transformar esto directamente en iteración. En su lugar, debe construir su propia pila para mantener el estado de cada llamada.

Answer 3

Estrictamente hablando, la recursión y la iteración son igualmente poderosas. Cualquier solución recursiva puede implementarse como una solución iterativa con una pila. La transformación inversa puede ser más complicada, pero lo más trivial es simplemente pasar el estado a través de la cadena de llamadas.

En Java, hay una situación en la que una solución recursiva es mejor que una iterativa (ingenua), y una situación en la que son básicamente equivalentes. En la mayoría de los otros casos, la solución iterativa será superior, ya que se evita la sobrecarga de llamadas a la función.

Si la función usa una pila implícitamente, la solución recursiva será generalmente superior. Considere una búsqueda en profundidad:

void walkTree(TreeNode t) {
    doSomething(t);

    if (t.hasLeft()) { walkTree(t.getLeft()); }
    if (t.hasRight()) { walkTree(t.getRight()); }
}

en comparación con la solución iterativa equivalente

void walkTree(TreeNode t) {
    Stack<TreeNode> s = new Stack<TreeNode>();
    s.push(t);
    while (!s.empty()) {
        TreeNode t = s.pop();
        doSomething(t);
        if (t.hasLeft()) { s.push(t.getLeft()); }
        if (t.hasRight()) { s.push(t.getRight()); }
    }
}

En el caso iterativo, tendrá que pagar por cualquier basura creada por el objeto Stack<> . En el caso recursivo, utilizará la pila de proceso, que no creará ninguna basura ni asignará ninguna memoria. La solución recursiva es vulnerable a un desbordamiento de pila, pero de lo contrario se ejecutará más rápido.

Si la función usa la recursión de la cola, entonces las dos soluciones serán equivalentes porque el JIT transformará el recursivo en el iterativo. La recursión de cola es cuando lo último que hace una función es invocarse de forma recursiva, lo que permite al compilador ignorar cualquier estado acumulado. Por ejemplo, atravesando una lista

void walkList(ListNode n) {
    doSomething(n);
    if (n.hasNext()) { walkList(n.getNext()); }
}

Ya que "walkList" es lo último que se hace en la función, el JIT lo transformará esencialmente en un "n = n.getNext (); goto begin", que lo hará equivalente a la solución iterativa.

En la mayoría de las otras situaciones, una solución iterativa será superior. Por ejemplo, si desea hacer una búsqueda en primer lugar, entonces podría usar una Queue lugar de una Stack en la solución iterativa, y hacer que funcione de manera instantánea, mientras que transformarla en una solución recursiva requiere que pague tanto lo implícito apilar en la pila de llamadas, y todavía pagar por la cola.

Answer 4

La declaración, "La recursión siempre es mejor que la iteración" es falsa. Hay casos en que cualquiera de los dos es preferible sobre el otro.

Es difícil darle una respuesta decisiva sobre qué tipo de algoritmo usar, ya que depende del caso particular. Por ejemplo, el caso común de recursión de libros de texto de la secuencia de Fibonacci es increíblemente ineficiente al usar la recursión, por lo que es mejor usar la iteración en ese caso. Por el contrario, atravesar un árbol puede implementarse de manera más eficiente utilizando la recursión.

Para responder a su segunda pregunta, sí, cualquier algoritmo iterativo puede implementarse usando recursión y viceversa.

Answer 5

Por lo general, los métodos recursivos exigen unas pocas líneas de código, pero un pensamiento profundo sobre su algoritmo. Si comete un error lógico, probablemente obtendrá un Error .

Aquí sigue 2 ejemplos de programación para factorial:

Iteractivo

public int calculateIteractiveFactorial(int n) {
    // Base case
    if (n == 1) {
        return 1;
    }
    int factorial = 1;
    for (int i = 1; i <= n; i++) {
        factorial = factorial * i;
    }
    return factorial;
}

Recursivo

public int calculateRecursiveFactorial(int n) {
    // Base case
    if (n == 1) {
        return 1;
    }
    return n * calculateRecursiveFactorial(n - 1);
}

Siempre es bueno reflexionar sobre diferentes ideas para cada propuesta, siempre considerando líneas de código, complejidad, claridad, cohesión, etc.

Answer 6

Si recordamos el mecanismo de paso por valor de Java, podemos entender que la recursión consume más memoria, ya que para cada llamada se pasa una copia de la dirección de referencia del objeto o un valor de algún tipo primitivo. Por lo tanto, como parámetros de mach que pasa para cada llamada recursiva como memoria de mach que consumirá para cada llamada, por otro lado, los bucles son fáciles de usar. Pero, por supuesto, sabemos que hay algoritmos de "divide y vencerás", por ejemplo, Mergesort o iteraciones en los árboles que consumen menos pasos con la ayuda de la recursión para dar un resultado. Así que en estos casos creo que es mejor usar la recursión.

Answer 7

que quieres decir mejor Cada recursión también se puede implementar con iteraciones y viceversa. A veces la recursión es más fácil de entender. sin embargo, dado que la recursión infla la pila, muchas llamadas anidadas pueden causar una excepción de falta de memoria. En este caso, la recursión no es su mejor opción.

Answer 8

La recursión es buena para que los programadores entiendan un programa, pero muchas veces provocan flujos de desbordamiento de pila, por lo que siempre prefieren la iteración sobre ellos .

El hecho es que la recursión rara vez es el enfoque más eficiente para resolver un problema, y ​​la iteración es casi siempre más eficiente. Esto se debe a que generalmente hay más gastos generales asociados con hacer llamadas recursivas debido al hecho de que la pila de llamadas se usa mucho durante la recursión.
Esto significa que muchos lenguajes de programación de computadora pasarán más tiempo manteniendo la pila de llamadas que en realidad realizarán los cálculos necesarios.

¿La recursión usa más memoria que iteración? En términos generales, sí lo hace. Esto se debe al uso extensivo de la pila de llamadas.

¿Debo usar la recursión o iteración?

La recursión generalmente se usa debido a que es más simple de implementar y, por lo general, es más "elegante" que las soluciones iterativas. Recuerde que todo lo que se hace en recursión también se puede hacer de forma iterativa, pero con la recursión generalmente hay un inconveniente en el rendimiento. Pero, dependiendo del problema que esté tratando de resolver, el inconveniente del rendimiento puede ser muy insignificante, en cuyo caso tiene sentido usar la recursión. Con la recursión, también obtiene el beneficio adicional de que otros programadores pueden entender su código más fácilmente, lo que siempre es bueno tener.