Recursión o bucles while

123

Estaba leyendo sobre algunas prácticas de desarrollo de entrevistas, específicamente sobre las preguntas técnicas y las pruebas que se hicieron en las entrevistas y me he tropezado varias veces con los dichos del género "Ok, resolviste el problema con un bucle while, ahora puedes hacerlo con recursividad ", o" todos pueden resolver esto con un bucle while de 100 líneas, pero ¿pueden hacerlo en una función recursiva de 5 líneas? " etc.

Mi pregunta es, ¿es la recursividad generalmente mejor que si / while / for constructs?

Honestamente, siempre he pensado que no es preferible la recursión, ya que está limitada a la memoria de la pila, que es mucho más pequeña que el montón, también hacer una gran cantidad de llamadas a funciones / métodos es subóptima desde el punto de vista del rendimiento, pero puedo estar equivocado...

Shivan Dragon
fuente
73
Sobre el tema de la recursividad, esto parece bastante interesante.
dan_waterworth
44
@dan_waterworth también, esto ayudaría: google.fr/… pero siempre parece que lo deletreo mal : P
Shivan Dragon
@ShivanDragon pensé que sí ^ _ ^ Muy apropiado que lo publiqué ayer :-)
Neal
2
En los entornos incrustados en los que he trabajado, la recursión está mal vista en el mejor de los casos y te azota públicamente en el peor de los casos. El espacio de pila limitado en efecto lo hace ilegal.
Fred Thomsen

Respuestas:

192

La recursión no es intrínsecamente mejor o peor que los bucles: cada uno tiene ventajas y desventajas, y estos incluso dependen del lenguaje de programación (y 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, regresar y retroceder de la pila OTOH, se pueden escribir muchos casos de recursión (especialmente aquellos que son trivialmente equivalentes a bucles iterativos) para evitar el stack push / pop; Esto es posible cuando la llamada de función recursiva es lo último que sucede en el cuerpo de la función antes de regresar, y se conoce comúnmente como una optimización de llamada de cola (u optimización de recursión de cola ). Una función recursiva optimizada correctamente para la cola de llamadas es en su mayoría equivalente a un bucle iterativo en el 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 cual los lenguajes puros como Haskell no tienen construcciones de bucle, 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, necesita una comprensión profunda de muchos conceptos vitales de programación (variables, llamadas a funciones, alcance y, por supuesto, bucles y recursión), y tiene para llevar a la mesa la flexibilidad mental 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 divisoria entre las personas que tienen la capacidad de comprender las variables, los punteros y la recursividad, y los que no. Casi todo lo demás en programación, incluidos los marcos, las API, los lenguajes de programación y sus casos límite, se pueden adquirir a través del estudio y la experiencia, pero si no puede desarrollar una intuición para estos tres conceptos básicos, no está en condiciones de ser un programador. La traducción de un bucle iterativo simple a una versión recursiva es la forma más rápida posible de filtrar a los que no son programadores; incluso un programador bastante inexperto generalmente puede hacerlo en 15 minutos, y es un problema muy agnóstico del lenguaje, por lo que el candidato puede elegir un idioma de su elección en lugar de tropezar con idiosincrasias.

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.

tdammers
fuente
3
Me gusta más su respuesta, porque toca los aspectos más importantes que podría tener una respuesta a esta pregunta, explica las partes técnicas principales y también ofrece una buena visión ampliada de cómo encaja este problema en la esfera de la programación.
Shivan Dragon
1
También he notado un patrón en una programación de sincronización donde se evitan los bucles a favor de las llamadas recursivas en un iterador que contiene un método .next (). Supongo que evita que el código de larga ejecución se vuelva demasiado codicioso de la CPU.
Evan Plaice el
1
La versión iterativa también implica empujar y reventar valores. Solo tiene que escribir manualmente el código para hacer esto. La versión recursiva está presionando el estado en la pila en un algoritmo iterativo que generalmente tiene que simular manualmente presionando el estado en una estructura. Solo los algoritmos más triviales no necesitan este estado y, en estos casos, el compilador generalmente puede detectar la recursión de la cola y plantar una solución iterativa.
Martin York
1
@tdammers ¿Podría decirme dónde puedo leer el estudio que mencionó "La experiencia y la investigación sugieren que hay una línea entre las personas ..." Esto parece ser muy interesante para mí.
Yoo Matsuo
2
Una cosa que olvidó mencionar, el código iterativo tiende a funcionar mejor cuando se trata de un solo hilo de ejecución, pero los algoritmos recursivos tienden a ejecutarse en múltiples hilos.
GordonM
37

Depende.

  • Algunos problemas son muy susceptibles a soluciones recursivas, por ejemplo, quicksort
  • Algunos idiomas realmente no admiten la recursividad, por ejemplo, los primeros FORTRAN
  • Algunos idiomas asumen la recursividad como un medio principal para el bucle, por ejemplo, Haskell

También vale la pena señalar que el soporte para la recursión de la cola hace que la cola recursiva y los bucles iterativos sean equivalentes, es decir, la recursión no siempre tiene 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, me gustaría señalar que una solución de cinco líneas es probablemente siempre mejor que una de 100 líneas (suponiendo que en realidad sean equivalentes).

jk.
fuente
55
Buena respuesta (+1). "una solución de 5 líneas es probablemente siempre mejor que una de 100 líneas": creo que la concisión no es la única ventaja de la recursividad. El uso de una llamada recursiva lo obliga a hacer explícitas las dependencias funcionales entre valores en diferentes iteraciones.
Giorgio el
44
Las soluciones más cortas tienden a ser mejores, pero existe la posibilidad de ser demasiado conciso.
dan_waterworth
55
@dan_waterworth en comparación con "100 line" es bastante difícil ser demasiado conciso
mosquito
44
@ Jorge, puede hacer que los programas sean más pequeños eliminando código innecesario o haciendo que las cosas explícitas estén implícitas. Mientras te quedes con lo primero, mejorarás la calidad.
dan_waterworth
1
@jk, creo que esa es otra forma de hacer que la información explícita sea implícita. La información sobre para qué se usa una variable se elimina de su nombre donde es explícita y se empuja a su uso implícito.
dan_waterworth
17

No existe una definición universalmente aceptada de "mejor" cuando se trata de programación, pero lo consideraré como "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 generalmente son algo malo porque te permiten hacer cosas que son difíciles de leer. Sin embargo, la recursividad te da la capacidad de escribir bucles sin usar la mutabilidad y, en mi opinión, la mutabilidad es mucho más poderosa que la recursividad.

Entonces, desde un bajo poder expresivo hasta un alto poder expresivo, las construcciones en bucle se acumulan así:

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

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

dan_waterworth
fuente
1
"un bucle while es equivalente a una función recursiva de cola y las funciones recursivas no necesitan ser recursivas de cola": +1. Puede simular la recursión mediante un ciclo while + una pila.
Giorgio
1
No estoy seguro de estar de acuerdo al 100%, pero sin duda es una perspectiva interesante, así que +1 para eso.
Konrad Rudolph el
+1 para una excelente respuesta y también para mencionar que algunos lenguajes (o compiladores) no hacen optimizaciones de llamadas de cola.
Shivan Dragon
@Giorgio, "Puedes simular la recursión por medio de un bucle while + una pila", por eso dije poder expresivo. Computacionalmente, son igualmente poderosos.
dan_waterworth
@dan_waterworth: Exactamente, y como dijiste en tu respuesta, la recursión sola es más expresiva que un ciclo while porque necesitas agregar una pila a un ciclo while para simular la recursividad.
Giorgio el
7

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, deja perfectamente claro que está escribiendo un bucle. Si escribe somefunction(ITER_LIMIT);, realmente no deja en claro lo que sucederá. Solo ver contenido: esa somefunction(int x)llamada somefunction(x-1)te dice que, de hecho, es un bucle que usa iteraciones. Además, no puede poner fácilmente una condición de escape en break;algún lugar a la mitad de las iteraciones, debe agregar un condicional que se pasará por completo o lanzar una excepción. (y las excepciones vuelven a agregar complejidad ...)

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

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

Hay situaciones en las que la recursividad 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 atraviesa un camino recto conocido, repita. Si se sumerge en lo desconocido, recurse.

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

... Escribir iterativamente funciones para tareas que se realizan mejor por 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 para fines prácticos. Puedo asegurarle que una vez que enfrente una tarea de este tipo, no tendrá dudas como las que expresó.

SF.
fuente
10
Lo que es obvio y lo que es menos obvio depende en parte de lo que está acostumbrado. La iteración se ha utilizado con mayor frecuencia en lenguajes de programación porque está más cerca de la forma de trabajar de la CPU (es decir, usa menos memoria y se ejecuta más rápido). Pero si estás acostumbrado a pensar inductivamente, la recursión puede ser tan intuitiva.
Giorgio el
55
"Si ven una palabra clave de bucle, saben que es un bucle. Pero no hay una palabra clave recurrente, pueden reconocerla solo al ver f (x-1) dentro de f (x)": cuando llamas a una función recursiva No quiero saber que es recursivo. Del mismo modo, cuando llama a una función que contiene un bucle, no desea saber que contiene un bucle.
Giorgio
3
@SF: Sí, pero solo puede ver esto si observa el cuerpo de la función. En caso de un bucle, verá el bucle, en caso de recursión, verá que la función se llama a sí misma.
Giorgio
55
@SF: Me parece un poco un razonamiento circular: "Si en mi intuición es un bucle, entonces es un bucle". mappuede definirse como una función recursiva (ver, por ejemplo, haskell.org/tutorial/functions.html ), incluso si es intuitivamente claro que atraviesa una lista y aplica una función a cada miembro de la lista.
Giorgio
55
@SF, mapno es una palabra clave, es una función regular, pero eso es un poco irrelevante. Cuando los programadores funcionales usan la recursión, generalmente no es porque quieran realizar una secuencia de acciones, sino porque el problema que se está resolviendo puede expresarse como una función y una lista de argumentos. El problema puede reducirse a otra función y a otra lista de argumentos. Eventualmente, tiene un problema que puede resolverse de manera trivial.
dan_waterworth
6

Como de costumbre, esto no se puede responder 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. Estas son algunas de las presiones.

  • El código corto y elegante es en general superior al código largo e intrincado.
  • Sin embargo, el último punto queda algo invalidado si su base de desarrolladores no está familiarizada con la recursividad y no quiere / no puede aprender. Incluso puede convertirse en un ligero negativo en lugar de positivo.
  • La recursión puede ser mala para la eficiencia si necesita llamadas anidadas en la práctica y no puede usar la recursión de cola (o su entorno no puede optimizar la recursión de cola).
  • La recursión también es mala en muchos casos si no puede almacenar en caché correctamente los resultados intermedios. Por ejemplo, el ejemplo común de usar la recursión de árbol para calcular los números de Fibonacci funciona terriblemente mal si no almacena en caché. Si haces caché, es simple, rápido, elegante y completamente maravilloso.
  • La recursión no es aplicable a algunos casos, tan buena como la iteración en otros, y absolutamente necesaria en otros. La recursión no suele ayudar a atravesar largas cadenas de reglas comerciales. La iteración a través de flujos de datos se puede hacer útilmente con recursividad. Iterar sobre estructuras de datos dinámicos multidimensionales (por ejemplo, laberintos, árboles de objetos ...) es prácticamente imposible sin recursividad, explícito o implícito. Tenga en cuenta que en estos casos, la recursividad explícita es mucho mejor que la 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 la palabra R aterradora.
Kilian Foth
fuente
¿Qué quiere decir con almacenamiento en caché en relación con la recursividad?
Giorgio
@Giorgio presumiblemente memoración
jk.
Feh Si su entorno no optimiza las llamadas de cola, debería encontrar un mejor entorno, y si sus desarrolladores no están familiarizados con la recurrencia, debería encontrar mejores desarrolladores. ¡Ten algunos estándares, gente!
CA McCann
1

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

Debería mencionarse también sobre el desbordamiento de la pila - http://en.wikipedia.org/wiki/Stack_overflow

okobaka
fuente
1
Recursión significa una función cuya definición implica llamarse a sí misma.
Hardmath
1
Si bien su definición simple no es exactamente 100% precisa, usted es el único que mencionó desbordamientos de pila.
Qix
1

Realmente depende de la conveniencia o el requisito:

Si toma el lenguaje de programación Python , es compatible con la recursividad, pero de forma predeterminada hay un límite para la profundidad de recursión (1000). Si excede 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.

usernaveen
fuente
3
Aquí hay un blog de Guido van Rossum sobre por qué no quiere la optimización de recursión de cola en Python (apoyando la noción de que los diferentes lenguajes adoptan enfoques tácticos distintos).
duro
-1

Usa el patrón de diseño de la estrategia.

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

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

Pravin Sonawane
fuente
55
¿Esperar lo? ¿Cómo encaja el patrón de estrategia aquí? Y la segunda oración suena como una frase vacía.
Konrad Rudolph el
@KonradRudolph Me gustaría recurrir. Para conjuntos de datos muy grandes, cambiaría a bucles. A eso me refería. Pido disculpas si no estaba claro.
Pravin Sonawane
3
Ah Bueno, todavía no estoy seguro de que esto pueda llamarse "patrón de diseño de estrategia", que tiene un significado muy fijo y lo usa metafóricamente. Pero ahora al menos veo a dónde vas.
Konrad Rudolph el
@KonradRudolph aprendió una lección importante. Explica profundamente lo que quieres decir ... Gracias ... eso ayudó ... :)
Pravin Sonawane
2
@Pravin Sonawane: si puede usar la optimización de recursión de cola, también puede usar la recursividad en grandes conjuntos de datos.
Giorgio el