Recursividad vs bucles

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; } 

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 stack, 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.

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 stack.

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.

La recursión se usa para express 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 progtwigció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.

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.

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.

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 stacks (esquema LIFO) para hacer que los bucles funcionen

En Java, las stacks están cubiertas con la interfaz Deque

 // Get all the writable folders under one folder // java-like pseudocode void searchWritableDirs(Folder rootFolder){ List response = new List(); // Results Deque folderDeque = new Deque(); // 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 response = new List(); // Results rec_searchWritableDirs(actualSubFolder,response); log("Folders " + response.size()); } private void rec_searchWritableDirs(Folder actual,List 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.

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.

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 progtwigdor 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 stack.

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.

Encuentro que la recursión es más natural, pero es posible que se vea obligado a utilizar el ciclo si su comstackdor no realiza la optimización de la cola y su árbol / lista es demasiado profunda para el tamaño de la stack.

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 progtwig envíe todos los parámetros y direcciones desagradables a la stack).

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.

Si su código está comstackdo, probablemente hará poca diferencia. Realice algunas pruebas y vea cuánta memoria se usa y qué tan rápido se ejecuta.

Si el sistema en el que está trabajando tiene una pequeña stack (sistemas integrados), la profundidad de recursión sería limitada, por lo que sería deseable elegir el algoritmo basado en bucle.

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; } 

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 fotogtwig en la memoria de stack 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:

• StackOverFlow cuando la stack 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 locking 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 StackOverFlow en un segundo y tal vez OutOfMemory también

Haz el segundo:

 while(true){ } 

El software se congelará y no se producirá ningún locking:

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

Asignación de memoria basada en stack

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.