algorithm - ventaja - recursión versus iteración
ventajas y desventajas de la recursividad (10)
¿Es correcto decir que en cualquier lugar en que se utilice la recursión se podría usar un bucle for?
Sí, porque la recursividad en la mayoría de las CPU se modela con bucles y una estructura de datos de pila.
Y si la recursividad es generalmente más lenta, ¿cuál es el motivo técnico para usarla?
No es "generalmente más lento": es la recursión que se aplica de manera incorrecta, que es más lenta. Además de eso, los compiladores modernos son buenos para convertir algunas repeticiones en bucles sin siquiera preguntar.
Y si siempre es posible convertir una recursividad en un bucle for, ¿existe una regla de oro para hacerlo?
Escribir programas iterativos para algoritmos que se entienden mejor cuando se explican de forma iterativa; escribir programas recursivos para algoritmos mejor explicados recursivamente.
Por ejemplo, buscar árboles binarios, ejecutar quicksort y analizar expresiones en muchos lenguajes de programación a menudo se explica recursivamente. Estos también están mejor codificados recursivamente. Por otro lado, calcular factoriales y calcular números de Fibonacci son mucho más fáciles de explicar en términos de iteraciones. Usar recursion para ellos es como golpear moscas con un mazo: no es una buena idea, incluso cuando el martillo hace un trabajo realmente bueno en eso + .
+ Tomé prestada la analogía del mazo de la "Disciplina de programación" de Dijkstra. ¿Es correcto decir que en cualquier lugar en que se utilice la recursion se podría usar un bucle for? Y si la recursividad suele ser más lenta, ¿cuál es el motivo técnico por el que nunca se ha utilizado para la iteración de bucle?
Y si siempre es posible convertir una recursividad en un bucle for, ¿existe una regla de oro para hacerlo?
Pregunta:
Y si la recursividad suele ser más lenta, ¿cuál es el motivo técnico por el que nunca se ha utilizado para la iteración de bucle?
Responder :
Porque en algunos algoritmos es difícil de resolver de forma iterativa. Intente resolver la búsqueda de profundidad primero tanto de forma recursiva como iterativa. Te darás cuenta de que es difícil de resolver DFS con iteración.
Otra cosa buena para probar: intente escribir Merge sort iteratively. Te llevará bastante tiempo.
Pregunta:
¿Es correcto decir que en cualquier lugar en que se utilice la recursión se podría usar un bucle for?
Responder :
Sí. Este thread tiene una muy buena respuesta para esto.
Pregunta:
Y si siempre es posible convertir una recursividad en un bucle for, ¿existe una regla de oro para hacerlo?
Responder :
Créeme. Intenta escribir tu propia versión para resolver la búsqueda en profundidad iterativamente. Notarás que algunos problemas son más fáciles de resolver recursivamente.
Sugerencia: la recursividad es buena cuando se está resolviendo un problema que se puede resolver mediante la técnica de dividir y conquistar .
Además de ser más lento, la recursión también puede dar como resultado errores de desbordamiento de pila dependiendo de qué tan profundo vaya.
La mayoría de las respuestas parecen suponer que iterative = for loop . Si su bucle for no está restringido ( a la C, puede hacer lo que quiera con su contador de bucle), entonces eso es correcto. Si se trata de un bucle real (por ejemplo, como en Python o en la mayoría de los lenguajes funcionales donde no se puede modificar manualmente el contador de bucles), entonces no es correcto.
Todas las funciones (computables) se pueden implementar recursivamente y usando while loops (o saltos condicionales, que son básicamente lo mismo). Si realmente se restringe a for loops , solo obtendrá un subconjunto de esas funciones (las primitivas recursivas, si sus operaciones elementales son razonables). De acuerdo, es un subconjunto bastante grande que contiene todas las funciones que es probable que encuentres en la práctica.
Lo que es mucho más importante es que muchas funciones son muy fáciles de implementar de manera iterativa y recursiva y terriblemente difíciles de implementar (la administración manual de su pila de llamadas no cuenta).
La recursividad suele ser mucho más lenta porque todas las llamadas a funciones deben almacenarse en una pila para permitir el retorno a las funciones de la persona que llama. En muchos casos, la memoria debe asignarse y copiarse para implementar el aislamiento del alcance.
Algunas optimizaciones, como la optimización de la cola de llamadas , hacen que las recursiones sean más rápidas, pero no siempre son posibles, y no están implementadas en todos los idiomas.
Las principales razones para usar la recursividad son
- que es más intuitivo en muchos casos cuando imita nuestro enfoque del problema
- que algunas estructuras de datos como los árboles son más fáciles de explorar utilizando la recursión (o que en cualquier caso necesitarían pilas)
Por supuesto, cada recursión se puede modelar como una especie de bucle: eso es lo que la CPU finalmente hará. Y la recursividad en sí, más directamente, significa colocar las llamadas de funciones y los ámbitos en una pila. Pero cambiar su algoritmo recursivo por uno bucle puede requerir mucho trabajo y hacer que su código sea menos sostenible: como para cada optimización, solo debe intentarse cuando algún perfil o evidencia lo demuestre necesario.
Me parece recordar que mi profesor de informática dice que todos los problemas que tienen soluciones recursivas también tienen soluciones iterativas. Él dice que una solución recursiva suele ser más lenta, pero se usan con frecuencia cuando son más fáciles de razonar y codificar que las soluciones iterativas.
Sin embargo, en el caso de las soluciones recursivas más avanzadas, no creo que siempre sea capaz de implementarlas utilizando un simple bucle for .
Para escribir un método equivalente usando iteración, debemos usar explícitamente una pila. El hecho de que la versión iterativa requiera una pila para su solución indica que el problema es tan difícil que puede beneficiarse de la recursión. Como regla general, la recursividad es más adecuada para problemas que no se pueden resolver con una cantidad fija de memoria y, en consecuencia, requieren una pila cuando se resuelven de forma iterativa. Una vez dicho esto, la recursión y la iteración pueden mostrar el mismo resultado mientras siguen un patrón diferente. Decidir qué método funciona mejor es caso por caso y la mejor práctica es elegir según el patrón que sigue el problema.
Por ejemplo, para encontrar el n-ésimo número triangular de secuencia triangular: 1 3 6 10 15 ... Un programa que usa un algoritmo iterativo para encontrar el n-ésimo número triangular:
Usando un algoritmo iterativo:
//Triangular.java
import java.util.*;
class Triangular {
public static int iterativeTriangular(int n) {
int sum = 0;
for (int i = 1; i <= n; i ++)
sum += i;
return sum;
}
public static void main(String args[]) {
Scanner stdin = new Scanner(System.in);
System.out.print("Please enter a number: ");
int n = stdin.nextInt();
System.out.println("The " + n + "-th triangular number is: " +
iterativeTriangular(n));
}
}//enter code here
Usando un algoritmo recursivo:
//Triangular.java
import java.util.*;
class Triangular {
public static int recursiveTriangular(int n) {
if (n == 1)
return 1;
return recursiveTriangular(n-1) + n;
}
public static void main(String args[]) {
Scanner stdin = new Scanner(System.in);
System.out.print("Please enter a number: ");
int n = stdin.nextInt();
System.out.println("The " + n + "-th triangular number is: " +
recursiveTriangular(n));
}
}
Respuesta corta: la compensación es la recursión más rápida y los bucles ocupan menos memoria en casi todos los casos. Sin embargo, generalmente hay formas de cambiar el bucle for o recursión para que funcione más rápido
Sí, como share ,
La recursividad es buena cuando se está resolviendo un problema que se puede resolver mediante la técnica de dividir y conquistar.
Por ejemplo: Torres de Hanoi
- N anillos en tamaño creciente
- 3 polos
- Los anillos comienzan apilados en la pole 1. El objetivo es mover los anillos para que estén apilados en la pole 3 ... Pero
- Solo puede mover un anillo a la vez.
- No se puede poner un anillo más grande encima de más pequeño.
- La solución iterativa es "poderosa pero fea"; la solución recursiva es "elegante".
recursión + memorización podría conducir a una solución más eficiente comparar con un enfoque iterativo puro, por ejemplo, verifique esto: http://jsperf.com/fibonacci-memoized-vs-iterative-for-large-n