Recursion o mientras bucles

La recursión no es intrínsecamente mejor o peor que los bucles: cada uno tiene ventajas y desventajas, e incluso dependen del lenguaje de programación (y de la implementación).

Técnicamente, los bucles iterativos se ajustan mejor a los sistemas informáticos típicos a nivel de hardware: a nivel de código de máquina, un bucle es solo una prueba y un salto condicional, mientras que la recursión (implementada ingenuamente) implica empujar un marco de pila, saltar, volver, y saltando de la pila. OTOH, muchos casos de recursión (especialmente aquellos que son trivialmente equivalentes a los bucles iterativos) se pueden escribir para que se pueda evitar el push / pop de la pila; esto es posible cuando la llamada a la función recursiva es lo último que sucede en el cuerpo de la función antes de regresar, y se conoce comúnmente como optimización de la llamada de la cola (o optimización de la recursión de la cola ) . Una función recursiva optimizada para una llamada de cola adecuada es casi siempre equivalente a un bucle iterativo a nivel de código de máquina.

Otra consideración es que los bucles iterativos requieren actualizaciones de estado destructivas, lo que los hace incompatibles con la semántica del lenguaje puro (sin efectos secundarios). Esta es la razón por la que los lenguajes puros como Haskell no tienen construcciones de bucles en absoluto, y muchos otros lenguajes de programación funcional los carecen por completo o los evitan tanto como sea posible.

Sin embargo, la razón por la que estas preguntas aparecen tanto en las entrevistas es porque para responderlas, se necesita una comprensión profunda de muchos conceptos de programación vitales: variables, llamadas a funciones, alcance y, por supuesto, ciclos y recursiones. y tiene que llevar la flexibilidad mental a la tabla que le permite abordar un problema desde dos ángulos radicalmente diferentes, y moverse entre diferentes manifestaciones del mismo concepto.

La experiencia y la investigación sugieren que existe una línea entre las personas que tienen la capacidad de comprender las variables, los indicadores y la recursión y las que no. Casi todo lo demás en programación, incluidos los marcos de trabajo, las API, los lenguajes de programación y sus casos extremos, puede adquirirse a través del estudio y la experiencia, pero si no puede desarrollar una intuición para estos tres conceptos básicos, no es apto para ser programador. Traducir un simple bucle iterativo a una versión recursiva es la forma más rápida de filtrar a los no programadores: incluso un programador bastante inexperto puede hacerlo en 15 minutos, y es un problema muy independiente del lenguaje, por lo que el candidato puede elegir un idioma de su elección en lugar de tropezar con idiosyncracies.

Si recibe una pregunta como esta en una entrevista, es una buena señal: significa que el posible empleador está buscando personas que puedan programar, no personas que hayan memorizado el manual de una herramienta de programación.

Depende.

• Algunos problemas son muy susceptibles de soluciones recursivas, por ejemplo. quicksort
• Algunos idiomas no son compatibles con la recursión, por ejemplo. FORTRANs tempranos
• Algunos idiomas asumen la recursión como un medio principal para hacer bucles, por ejemplo. Haskell

También vale la pena señalar que el soporte para tail recursion hace que la cola sea recursiva e iterativa, es decir, la recursión no Siempre hay que desperdiciar la pila.

Además, un algoritmo recursivo siempre se puede implementar de forma iterativa mediante el uso de una pila explícita .

Finalmente, observaría que una solución de cinco líneas probablemente sea siempre mejor que una línea de 100 (asumiendo que en realidad son equivalentes).

No existe un acuerdo universal sobre la definición de "mejor" cuando se trata de programación, pero entenderé que significa "más fácil de mantener / leer".

La recursión tiene más poder expresivo que las construcciones de bucle iterativo: digo esto porque un bucle while es equivalente a una función recursiva de cola y las funciones recursivas no necesitan ser recursivas de cola. Las construcciones poderosas suelen ser algo malo porque te permiten hacer cosas que son difíciles de leer. Sin embargo, la recursión te da la capacidad de escribir bucles sin utilizar la mutabilidad y, en mi opinión, la mutabilidad es mucho más potente que la recursión.

Entonces, desde el poder expresivo bajo al poder expresivo alto, las construcciones en bucle se apilan así:

• Funciones recursivas de la cola que utilizan datos inmutables,
• Funciones recursivas que utilizan datos inmutables,
• Mientras que los bucles utilizan datos mutables,
• Funciones recursivas de la cola que utilizan datos mutables,
• Funciones recursivas que utilizan datos mutables,

Idealmente, usarías las construcciones menos expresivas que puedas. Por supuesto, si su idioma no admite la optimización de llamadas de cola, entonces eso también puede influir en su elección de construcción de bucle.

La recursión es a menudo menos obvia. Menos obvio es más difícil de mantener.

Si escribe for(i=0;i<ITER_LIMIT;i++){somefunction(i);} en el flujo principal, dejará perfectamente claro que está escribiendo un bucle. Si escribes somefunction(ITER_LIMIT); realmente no dejas en claro lo que sucederá. Solo se ve el contenido: somefunction(int x) calls somefunction(x-1) le dice que en realidad es un bucle que usa iteraciones. Además, no puede poner fácilmente una condición de escape con break; en algún lugar a mitad de las iteraciones, debe agregar un condicional que se pasará hasta el final o lanzar una excepción. (y las excepciones nuevamente agregan complejidad ...)

En esencia, si es una elección obvia entre iteración y recursión, haz lo intuitivo. Si la iteración hace el trabajo fácilmente, guardar 2 líneas rara vez vale la pena por los dolores de cabeza que puede crear a largo plazo.

Por supuesto, si te está ahorrando 98 líneas, es un asunto completamente diferente.

Hay situaciones en las que la recursión simplemente encaja perfectamente, y no son realmente infrecuentes. Recorrido de estructuras de árbol, redes de enlaces múltiples, estructuras que pueden contener su propio tipo, matrices dentadas multidimensionales, esencialmente cualquier cosa que no sea un vector directo o una matriz de dimensiones fijas. Si atraviesas un camino conocido, recto, itera. Si te sumerges en lo desconocido, repírate.

Esencialmente, si se debe llamar a somefunction(x-1) desde dentro de sí mismo más de una vez por nivel, olvida las iteraciones.

... Escribir funciones iterativas para tareas que se realicen mejor mediante recursión es posible pero no agradable. Donde sea que uses int , necesitas algo como stack<int> . Lo hice una vez, más como ejercicio que por razones prácticas. Puedo asegurarte que una vez que te enfrentes a esa tarea no tendrás dudas como las que expresaste.

Como es habitual, esto no tiene respuesta en general porque hay factores adicionales, que en la práctica son muy desiguales entre los casos y desiguales entre sí dentro de un caso de uso. Aquí están algunas de las presiones.

• El código corto y elegante en general es superior al código largo e intrincado.
• Sin embargo, el último punto se invalida de alguna manera si su base de desarrolladores no está familiarizada con la recursión y no está dispuesta / no puede aprender. Incluso puede convertirse en un leve negativo en lugar de un positivo.
• la recursión puede ser mala para la eficiencia si en la práctica necesitará llamadas profundamente anidadas y no puede usar la recursión de cola (o su entorno no puede optimizar la cola) recursión).
• La recursión también es mala en muchos casos si no puede almacenar correctamente los resultados intermedios. Por ejemplo, el ejemplo común de usar la recursión de árbol para calcular los números de Fibonacci hace que horriblemente sea malo si no se almacena en caché. Si haces caché, es simple, rápido, elegante y en conjunto maravilloso.
• La recursión no es aplicable a algunos casos, tan buena como la iteración en otros, y absolutamente necesaria en otros. Por lo general, la recursión no ayuda en absoluto a las largas cadenas de reglas comerciales. La iteración a través de flujos de datos puede ser útil con recursión. Iterar sobre estructuras de datos dinámicas multidimensionales (por ejemplo, laberintos, árboles de objetos ...) es prácticamente imposible sin recursión, explícita o implícita. Tenga en cuenta que en estos casos, la recursión explícita es mucho mejor que implícita; nada es más doloroso que leer el código donde alguien implementó su propia pila ad hoc, incompleta y con errores dentro del lenguaje, solo para evitar el miedo. -word.

La recursión se trata de repetir la llamada a la función, el bucle se trata de repetir el salto al lugar en la memoria.

También debería mencionarse sobre el desbordamiento de pila - enlace

Realmente depende de la conveniencia o el requisito:

Si tomas el lenguaje de programación Python , admite la recursión, pero por defecto hay un límite para la profundidad de recursión (1000). Si supera el límite, obtendremos un error o una excepción. Ese límite se puede cambiar, pero si lo hacemos, podemos experimentar situaciones anormales en el idioma.

En este momento (número de llamadas más que la profundidad de recursión), necesitamos preferir construcciones de bucle. Quiero decir, si el tamaño de la pila no es suficiente, tenemos que preferir las construcciones de bucle.

Utilice el patrón de diseño de estrategia.

• La recursión está limpia
• Los bucles son (posiblemente) eficientes

Dependiendo de su carga (y / u otras condiciones), elija una.