En la programación de computadoras, ¿es cierto que una recursión funcionará mejor para encontrar todas las rutas posibles que los bucles anidados?

Su pregunta debería ser ‘¿Por qué la recursividad es mejor que la iteración?’, No usar una recursión porque depende del tipo de lenguaje que esté utilizando, donde se puede afectar el rendimiento del uso de uno sobre otro. Al igual que la familia C, cuando la invocación de una función con / sin recursión crea un nuevo stackframe (espero que esté familiarizado con el stackframe) que, por supuesto, causará problemas de rendimiento.

Pero en otros idiomas este no es el caso, en esos idiomas, usar la recursión es mejor que la iteración.

Ahora venga a su pregunta principal, ¿por qué usar la recursividad para encontrar rutas en bucles? Si ve la recursión un poco más técnicamente, es como un bucle, comprueba si hay una o más condiciones si se cumple y luego se detiene, de lo contrario se llama de nuevo. Pero se piensa como un mejor enfoque para escenarios como encontrar caminos, resolver laberintos, juegos, el camino más corto, etc.

Te sugiero que codifiques tu algoritmo en ambos (con / sin recursión), compares tu rendimiento con su algoritmo y elijas el mejor de ellos, no te concentres en si lo necesitas o no.

Le sugiero que mire la excelente cobertura de Amit Patel sobre este tema: Introducción a A *. Es importante que tenga una manera de considerar múltiples rutas y de continuar desde una ruta anterior parcialmente completada. Esto normalmente se hace con una cola de rutas parciales y un solo bucle, no con una función recursiva, ni con bucles anidados.

Para un problema de búsqueda de ruta, las soluciones recursivas son más fáciles de escribir que las soluciones iterativas. Sin embargo, las soluciones iterativas tienden a ser un poco más rápidas suponiendo que no haya optimizaciones del compilador, porque cada llamada de función recursiva tiene algo de sobrecarga.

Por cierto, siempre que use una solución recursiva, siempre hay una versión iterativa que puede escribir. Intente pensar en términos de hacer estallar un nodo en una pila y luego procesarlo más tarde que los otros nodos que continuará procesando. Si usa una pila, también causará el mismo tipo de sobrecarga que sufren las llamadas a funciones recursivas.

Para agregar a (algunas) de las otras respuestas. Usar la recursividad generalmente significa dividir un problema en subproblemas naturales . En una solución en bucle, las iteraciones en sí mismas a menudo no resuelven ningún subproblema, debe pensar cómo la iteración contribuye a la solución completa … esto es difícil y, por lo tanto, propenso a errores.

Sobre la constante arpa de la eficiencia por parte de algunas personas. Cuando se trata de encontrar una solución a un problema, no es el momento de pensar en la eficiencia de la ejecución. La eficiencia de una solución consiste en

• Costo de desarrollo … cuánto esfuerzo necesito invertir
• Costo de prueba proyectado
• Costo de mantenimiento proyectado … ¿entenderá un mantenedor este código? ¿Lo entenderé dentro de unas semanas?
• ¿Su eficiencia de ejecución impacta materialmente en la solución general? Por ejemplo, si la solución está limitada por la latencia de la red, puede no importar si la solución recursiva es 100 veces más lenta que una de bucle.

Finalmente, si la respuesta a la última es sí … entonces puede invertir el tiempo para convertir la recursión en bucles. Pero estará muy por delante … ya sabe que ya tiene una solución que funciona.

No necesariamente. Esto se debe a que la recursión puede parecer tener una mejor complejidad temporal en el caso de un bucle anidado. Un bucle anidado, generalmente tiene una complejidad de tiempo [matemática] O (n ^ m) [/ matemática] en el peor de los casos, donde [matemática] m [/ matemática] es el número de bucles que están anidados dentro. Y un algoritmo recursivo ejecuta [matemática] O (n) [/ matemática], o una [matemática] O (lg n) [/ matemática] o [matemática] O (n lg n) [/ matemática] complejidad de tiempo cuando implementa Un paradigma de divide y vencerás. Entonces, aparentemente la recursión es mejor que los bucles anidados.

PERO

Hay otra cosa que debes tener en cuenta. Que, cada vez que se llama a una función de forma recursiva, los datos se introducen continuamente en la pila. Lo que significa que puede acumular datos y si la computadora no tiene suficiente memoria, o si el número de llamadas recursivas es demasiado grande, puede conducir a la situación llamada DESBORDAMIENTO DE PILA.

Por lo tanto, la iteración anidada y las llamadas recursivas son efectivas, pero cada una tiene sus propias ventajas y desventajas.

Espero que ayude.

Es cierto que los algoritmos recursivos suelen ser más fáciles de escribir, pero nunca funcionarán mejor que los bucles. Si lo desea, puede implementar un algoritmo recursivo con un bucle y una pila para realizar el mismo comportamiento.

Sin embargo, los algoritmos recursivos tienen varios inconvenientes:

1. no puede almacenar resultados temporales para programación dinámica. Sin embargo, supongo que no lo necesita en su caso.

2. tienes que realizar DFS en algoritmos recursivos, y no puedes salir por el medio.

3. gastará más recuerdos de pila, especialmente cuando el árbol es grande.

4. Los algoritmos recursivos no pueden ser optimizados por un compilador, mientras que los bucles sí.

Cuando estamos escribiendo bucles, significa que le decimos al programa que realice alguna secuencia de acciones, por ejemplo, para encontrar una suma de una matriz, decimos que agreguemos el primer valor a la suma, luego el segundo, luego el tercero, etc. . Por supuesto, puede hacer que este patrón sea más complicado con bucles anidados, pero todavía se trata de algunas secuencias de acciones similares realizadas en algún orden. Por lo tanto, los bucles serán más adecuados cuando esté escribiendo un código sobre el que está pensando intuitivamente, ya que algunas acciones se realizan muchas veces en secuencia.

Cuando escribe una función recursiva, mientras que, por supuesto, al final las piezas de su código se ejecutarán en alguna secuencia / orden, no es necesario que piense de antemano conscientemente sobre qué desea que sea esta orden. La recursividad le permite pensar que el problema es una llamada “forma de caja negra”: ” Quiero hacer alguna acción (encontrar la ruta desde el estado N) y para hacerlo podría necesitar también otros resultados (los resultados de encontrar rutas para los estados adyacentes a la mía), por lo que solo escribiré una llamada recursiva a mi función y puedo pensar en ello como si mágicamente obtuviera todos esos otros resultados correctos sin tener que hacer nada, y ahora solo puedo tome estos resultados calculados mágicamente y calcule mis resultados para el estado N de ellos “.

Así que, en particular, la recursividad de búsqueda de ruta es una herramienta mejor, porque cuando piensa en el algoritmo para la búsqueda de ruta no sabe en qué orden desea visitar los nodos; lo aprenderá sobre la marcha cuando visite un nodo y Tendrá que elegir alguna opción sobre dónde ir a continuación. Por supuesto, puede hacer esto con bucles (significará más o menos que escribirá bucles que simulan qué es la recursión), por lo que puede hacerse, pero no es así como puede pensar fácilmente sobre este problema. El pensamiento del “problema de la caja negra”, por otro lado, se aplica de manera muy intuitiva: si estoy parado en la intersección del laberinto, entonces no tengo idea de qué hacer, pero si alguien mágicamente me dijo cuánto tiempo dura el camino hacia la salida intersección vecina, entonces puedo decidir fácilmente a cuál de las intersecciones vecinas quiero ir. Lo único es que, en la práctica, alguien que mágicamente me dirá los resultados de esas otras intersecciones será mi función recursiva, que ahora estoy escribiendo para calcular el resultado ” solo para este nodo en el que estoy, suponiendo que para otro nodos podré obtener mágicamente el resultado s ”.

No, deberían funcionar más o menos igual. La principal diferencia es que la versión recursiva generalmente será más fácil de escribir y la versión iterativa generalmente será más fácil de optimizar. Sin embargo, estas diferencias no son muy grandes y pueden verse eclipsadas por las diferencias causadas por el lenguaje que está utilizando y los detalles de su algoritmo y datos.

Tenga en cuenta que no debería necesitar bucles anidados para buscar rutas. Puede hacerlo con un solo bucle y una pila o cola, de la misma manera que funciona la recursividad.

Tenga cuidado con su profundidad recursiva, alguna vez encontré una pregunta de entrevista sobre stackoverflow y heapoverflow, porque nunca conocí esa pregunta y nunca pensé en ese escenario, por lo que no pude responder, así que le pregunté al entrevistador su respuesta, y él me preguntó de otra manera: ¿quién tiene relación con la pila en Java, y sabía que era un método ejecutable, entonces sabía por qué? Si necesita lidiar con una gran cantidad de datos utilizando el algoritmo de fusión, entonces es un problema real de recursivo muy profundo y resulta en una excepción de stackoverflow. Así que dijiste que la recursión funciona mejor que otros bucles anidados, estoy de acuerdo contigo, pero no totalmente, depende de tu escena, pero como el libro de DS&A dice que el recursivo funciona mejor que el bucle.

No estoy de acuerdo en términos de tiempo y espacio, pero las implementaciones recursivas son más sencillas y fáciles de implementar.