recursion - usar - Recursividad vs bucles
ventajas y desventajas de la recursividad (15)
Estoy enfrentando un problema donde tanto la recursividad como el uso de un bucle parecen soluciones naturales. ¿Existe una convención o "método preferido" para casos como este? (Obviamente, no es tan simple como a continuación)
Recursión
Item Search(string desired, Scope scope) {
foreach(Item item in scope.items)
if(item.name == desired)
return item;
return scope.Parent ? Search(desired, scope.Parent) : null;
}
Lazo
Item Search(string desired, Scope scope) {
for(Scope cur = scope; cur != null; cur = cur.Parent)
foreach(Item item in cur.items)
if(item.name == desired)
return item;
return null;
}
Bueno, vi toneladas de respuestas e incluso acepté la respuesta, pero nunca vi la correcta y estaba pensando por qué ...
Larga historia corta :
¡Siempre evite recurrencias si puede hacer que la misma unidad sea producida por bucles!
¿Cómo funciona la recursividad?
• El fotograma en la memoria de pila se está asignando para una sola llamada de función
• El cuadro contiene referencia al método real
• Si el método tiene objetos, los objetos se colocarán en la memoria Heap y Frame contendrá una referencia a esos objetos en la memoria Heap.
• ¡Estos pasos se están realizando para cada llamada a un solo método!
Riesgos:
• cuando la pila no tiene memoria para poner nuevos métodos recursivos.
• OutOfMemory cuando el Heap no tiene memoria para colocar objetos almacenados recursivos.
¿Cómo funciona el bucle?
• Todos los pasos anteriores, excepto que la ejecución de código repetidamente dentro del ciclo no consumirá ningún dato adicional si ya se ha consumido.
Riesgos:
• El riesgo individual está dentro del ciclo cuando tu condición nunca existirá ... Bueno, eso no causará ningún bloqueo ni nada, simplemente no saldrá del ciclo si lo haces ingenuamente while(true) :)
Prueba:
Haz lo siguiente en tu software:
private Integer someFunction(){
return someFunction();
}
Obtendrá la excepción en un segundo y tal vez OutOfMemory también
Haz el segundo:
while(true){
}
El software se congelará y no se producirá ningún bloqueo:
Por último, pero no menos importante, for bucles:
Siempre vaya con bucles porque de alguna manera este bucle lo obliga a dar el punto de ruptura más allá del cual el bucle no irá, seguramente puede estar súper enojado y solo encontrar una manera de hacer bucle nunca se detiene, pero le aconsejo para usar siempre bucles en lugar de recurrencia en aras de la administración de la memoria y una mejor productividad para su software, que es un gran problema en estos días.
Referencias
Diría que la versión de recursión es más comprensible, pero solo con comentarios:
Item Search(string desired, Scope scope) {
// search local items
foreach(Item item in scope.items)
if(item.name == desired)
return item;
// also search parent
return scope.Parent ? Search(desired, scope.Parent) : null;
}
Es mucho más fácil explicar esta versión. Intenta escribir un buen comentario en la versión de bucle y verás.
Encuentro que la recursión es más natural, pero es posible que se vea obligado a utilizar el ciclo si su compilador no realiza la optimización de la cola y su árbol / lista es demasiado profunda para el tamaño de la pila.
Es demostrable que todos los algoritmos recursivos de cola se pueden desenrollar en un bucle, y viceversa. En términos generales, una implementación recursiva de un algoritmo recursivo es más clara a seguir para el programador que la implementación de bucle, y también es más fácil de depurar. También en términos generales, el rendimiento en el mundo real de la implementación del bucle será más rápido, ya que una bifurcación / salto en un bucle suele ser más rápido de ejecutar que empujar y hacer estallar un marco de pila.
Hablando en términos personales, para los algoritmos recursivos de cola prefiero seguir con la implementación recursiva en todas las situaciones menos en las que requieren más rendimiento.
Evita la recursividad. Lo más probable es que ese trozo de código deba mantenerse eventualmente en algún momento y será más fácil si no se realiza con recursividad. En segundo lugar, lo más probable es que tenga un tiempo de ejecución más lento.
La recursión se usa para expresar un algoritmo que es naturalmente recursivo en una forma que es más fácil de entender. Un algoritmo "naturalmente recursivo" es aquel en el que la respuesta se construye a partir de las respuestas a sub-problemas más pequeños que a su vez se construyen a partir de las respuestas a sub-problemas aún más pequeños, etc. Por ejemplo, computar un factorial.
En un lenguaje de programación que no es funcional, un enfoque iterativo es casi siempre más rápido y más eficiente que un enfoque recursivo, por lo que la razón para usar la recursión es claridad, no velocidad. Si una implementación recursiva termina siendo menos clara que una implementación iterativa, entonces, por supuesto, evítela.
En este caso particular, juzgaría que la implementación iterativa es más clara.
Por lo general, prefiero el uso de bucles. La mayoría de los buenos diseños de OOP le permitirán usar bucles sin tener que recurrir a la recursión (y por lo tanto, evitar que el programa envíe todos los parámetros y direcciones desagradables a la pila).
Tiene más uso en el código de procedimiento donde parece más lógico pensar de forma recursiva (debido a que no se puede almacenar fácilmente el estado o los metadatos (¿información?) Y así crear más situaciones que merecerían es uso).
La recursión es buena para escribir una función y / o escribir una base, pero después de saber que el código funciona y volver a él durante la fase de optimización, intente reemplazarlo por un bucle.
De nuevo, esto es todo obstinado. Ve con lo que funciona mejor para ti.
Prefiero bucles como
- La recursión es propensa a errores
- Todo el código permanece en una función / método
- Ahorro de memoria y velocidad
Yo uso pilas (esquema LIFO) para hacer que los bucles funcionen
En Java, las pilas están cubiertas con la interfaz Deque
// Get all the writable folders under one folder
// java-like pseudocode
void searchWritableDirs(Folder rootFolder){
List<Folder> response = new List<Folder>(); // Results
Deque<Folder> folderDeque = new Deque<Folder>(); // Stack with elements to inspect
folderDeque.add(rootFolder);
while( ! folderDeque.isEmpty()){
Folder actual = folder.pop(); // Get last element
if (actual.isWritable()) response.add(actual); // Add to response
for(Folder actualSubfolder: actual.getSubFolder()) {
// Here we iterate subfolders, with this recursion is not needed
folderDeque.push(actualSubfolder);
}
}
log("Folders " + response.size());
}
Menos complicado, más compacto que
// Get all the writable folders under one folder
// java-like pseudocode
void searchWritableDirs(Folder rootFolder){
List<Folder> response = new List<Folder>(); // Results
rec_searchWritableDirs(actualSubFolder,response);
log("Folders " + response.size());
}
private void rec_searchWritableDirs(Folder actual,List<Folder> response) {
if (actual.isWritable()) response.add(actual); // Add to response
for(Folder actualSubfolder: actual.getSubFolder()) {
// Here we iterate subfolders, recursion is needed
rec_searchWritableDirs(actualSubFolder,response);
}
}
Este último tiene menos código, pero tiene dos funciones y es más difícil de entender el código, en mi humilde opinión.
Si el rendimiento es importante, realice una evaluación comparativa de ambos y elija de forma racional. De lo contrario, elija en función de la complejidad, con la preocupación de un posible desbordamiento de pila.
Hay una guía del clásico libro The Elements of Programming Style (por Kernighan y Plauger) que el algoritmo debe seguir la estructura de datos. Es decir, las estructuras recursivas a menudo se procesan más claramente con algoritmos recursivos.
Si el sistema en el que está trabajando tiene una pequeña pila (sistemas integrados), la profundidad de recursión sería limitada, por lo que sería deseable elegir el algoritmo basado en bucle.
Si está utilizando un lenguaje funcional (no parece ser así), continúe con la recursión. De lo contrario, el bucle probablemente será mejor entendido por cualquier persona que trabaje en el proyecto. Por supuesto, algunas tareas (como buscar recursivamente en un directorio) son más adecuadas para la recursión que otras.
Además, si el código no se puede optimizar para la recursión final, el ciclo es más seguro.
Si su código está compilado, probablemente hará poca diferencia. Realice algunas pruebas y vea cuánta memoria se usa y qué tan rápido se ejecuta.
También puede escribir el bucle en un formato más legible. Las C de for(init;while;increment) tienen algunos inconvenientes de legibilidad ya que el comando de increment se menciona al inicio pero se ejecuta al final del ciclo.
Además, TUS DOS MUESTRAS NO SON EQUIVALENTES . La muestra recursiva fallará y el ciclo no lo hará, si lo llama como: Search(null,null) . Esto hace que la versión de bucle sea mejor para mí.
Aquí están las muestras modificadas (y suponiendo que null es falso)
Recursividad (fijo y de cola optimizable)
Item Search(string desired, Scope scope) {
if (!scope) return null
foreach(Item item in scope.items)
if(item.name == desired)
return item;
//search parent (recursive)
return Search(desired, scope.Parent);
}
Lazo
Item Search(string desired, Scope scope) {
// start
Scope cur = scope;
while(cur) {
foreach(Item item in cur.items)
if(item.name == desired)
return item;
//search parent
cur = cur.Parent;
} //loop
return null;
}
Usa el bucle Es más fácil de leer y entender (leer código siempre es mucho más difícil que escribirlo), y generalmente es mucho más rápido.
Yo prefiero las soluciones recursivas cuando:
La implementación de la recursión es mucho más simple que la solución iterativa, generalmente porque explota un aspecto estructural del problema de una manera que el enfoque iterativo no puede
Puedo estar razonablemente seguro de que la profundidad de la recursión no causará un desbordamiento de la pila, suponiendo que estamos hablando de un lenguaje que implemente la recursión de esta manera
La condición 1 no parece ser el caso aquí. La solución iterativa tiene el mismo nivel de complejidad, así que me quedaré con la ruta iterativa.