Informática: ¿Por qué la recursión es más elegante que la iteración?

La recursividad es más general.

Una solución iterativa está bien para datos que son lineales como matrices y listas enlazadas; o procesos que son lineales, como “haz esto 10 veces”.

Pero la iteración se vuelve cada vez más complicada cuando desea atravesar árboles u otras estructuras complejas de profundidades indefinidas. O desea hacer cosas que pueden ramificarse entre diferentes opciones en diferentes casos. O trampolín entre dos procesos complementarios.

A medida que aumenta la complejidad de sus datos / procesos, los enfoques recursivos tienden a realizar un seguimiento, escalando más o menos linealmente con el problema. Los enfoques iterativos pueden ir en espiral hacia sus propias complejidades combinatorias a medida que intentas escribir código adicional para aplanar los datos / tareas complejas en secuencias unidimensionales para que se puedan repetir.

Repetir es humano, recurrir divino.

Realmente se reduce a menos líneas de código y elegancia.

1)

int fact(int n)
{
return (n==1||n==0)?1:n*fact(n-1);
}


2)

hecho de hecho (int n)
{
int i, f = 1;
para (i = 1; i <= n; i ++)
f = f * i;
volver f;
}

Siempre elegiría 1 sobre 2.

La recursión no es fundamentalmente más elegante que la iteración, aunque puede ser más poderosa.

Los programadores funcionales tienden a preferir la recursividad porque la iteración suele ser una técnica imprescindible. Incluso si no considera que el contador de iteraciones en sí sea un estado modificado de forma imperativa, casi siempre hay algún estado que lleva entre iteraciones en el bucle.

La recursividad, por otro lado, le permite calcular el resultado del cómputo completo a partir de los resultados de subcomputaciones, lo cual es bueno para la programación funcional. También se generaliza a estructuras como los árboles, aunque la iteración a veces es más adecuada para conjuntos.

He hecho bastante programación funcional. A diferencia de la mayoría de los otros que respondieron a esta pregunta, me he encontrado con muchos casos en los que la iteración parece una solución más elegante para un problema que la recursividad. Pero a menudo no está disponible o al menos se desalienta debido a construcciones de lenguaje (te estoy mirando, Haskell), lo que puede resultar en un código mucho menos legible. Esto ocurre con mayor frecuencia cuando un algoritmo necesita rastrear muchos acumuladores, pero cada uno no se actualiza en la mayoría de las iteraciones.

No estoy de acuerdo con que se trate de la longitud del código. En mi opinión, es el hecho de que generalmente hay menos conceptos con los que lidiar.

Las soluciones recursivas tienen el mismo aspecto:

• Reduce el problema a una forma más simple.
• Identifique formas del problema que sean demasiado simples para reducirse.
• Resuelve las formas más simples del problema.
• Recopile y combine los resultados del componente.

Cuatro piezas (o dos piezas cada una con dos piezas, si lo prefiere) es una idea convincente, especialmente cuando esas partes son solo cosas que puede enchufar. No hay forma de descomponer una solución iterativa, simplemente … haga cosas … hasta que Ya terminaste.

Si le gusta la teoría de la complejidad, debería ser trivial escribir la relación de recurrencia (ya que cada pieza tiene una complejidad y la relación entre las partes es consistente), lo que significa que encontrar la complejidad general es solo matemática.

Menos código también es bueno, pero no es lo que yo llamaría elegante … o necesariamente cierto en todos los casos, especialmente si no puede aprovechar la pila del sistema.

La iteración es detallada, la recursividad es mucho más limpia.
Ambas técnicas logran el mismo objetivo, la llamada recursiva no le ahorra un espacio de almacenamiento, ya que en algún lugar debe mantenerse una pila de los valores que se procesan. Tampoco la recursión funcionará más rápido. La recursión es una iteración de aspecto sexy y mucho más legible, ya que al menos te ahorra una docena de líneas de código. Es especialmente conveniente para estructuras definidas recursivamente como, árboles y algoritmos de búsqueda, calculando los números de Fibonacci.

Al escribir una función recursiva, siempre debe buscar los puntos de ruptura, los casos de esquina de la llamada, de lo contrario, terminará en un bucle infinito que causará una falla de segmentación en algún momento. Primero capture los puntos de ruptura en alguna cláusula if / else y luego realice la llamada recursiva.
Hay un huevo de Pascua de Google Engineers … abre una pestaña de Chrome y busca la recursividad, ¿lo tienes? 😉

Hablando de estilos, la comprensión se usa ampliamente en Python.

Ambos son análogos. Muchas personas prefieren usar la recursión en lugar de la iteración, incluido yo. La razón detrás de esto es cómo miro el problema. Tomemos como ejemplo el recorrido en orden del árbol, cada hoja en un árbol es un árbol en sí mismo, por lo que puedo reducir mi árbol usando la recursión y la resultante será solo árbol.
Es fácil usar la recursividad en lenguaje de programación orientado a objetos, ¿cómo?
Una vez que tenga un objeto en su memoria, puede jugarlo como quiera.
Al leer el archivo xml, cada etiqueta en xml es xml en sí misma, por lo que podemos reducir xml usando recursividad.
La parte más importante es cómo se ve el problema. Si puede reducir el objeto a uno de su propio tipo, entonces recurra a la recursividad. Por cierto, cada algoritmo de recursión puede transformarse en uno con iteración.

Como dijo Andrew Bransford Brown, (a menudo) hay menos líneas de código.

Hay una diferencia entre elegante e inteligente, y algunos enfoques pueden ser inteligentes, pero no realmente elegantes. Por ejemplo, la recursividad no es más elegante si hace que la aplicación explote porque se repite demasiado.

La clave es que el enfoque que elija se ajuste a un enfoque natural, comprensible, funcional, eficiente y sostenible para resolver el problema.

La recursión es más poderosa pero tiene caídas propias. Esp, tiene una alta complejidad espacial en comparación con la iteración. También es más lento que la iteración. Sin embargo, hay ciertos problemas que no pueden abordarse mediante la iteración, por ejemplo. Encontrar todas las permutaciones posibles de una cadena de caracteres N. Aquí es más fácil hacer que el código sea más simple y limpio utilizando el enfoque recursivo en lugar del enfoque iterativo. Aquí hay una pequeña demostración donde he tratado de explicar algunos enfoques recursivos para resolver ciertos problemas:

Javascript – Introducción a la recursión – Golibrary.co

Cuando puede dividir un problema grande en problemas cada vez más pequeños hasta que puedan resolverse trivialmente, comienza a notar que esta es realmente la forma humana de resolver problemas.
Los humanos son, por defecto, más elegantes que las máquinas.

No lo son, son requisitos para diferentes tareas. Las tareas que necesitan recursividad generalmente no se pueden hacer con iteración lineal, y las tareas que se pueden manejar con iteración no se deben manejar con recursión.

Cuando la estructura de datos tiene forma de árbol, lo que significa que se puede estirar infinitamente en cualquier dirección y continuamente tener subnodos que pueden ramificarse de cualquier manera: use la recursividad.

Cuando la estructura de datos tiene 1, 2 o 3 dimensiones establecidas y predefinidas, use la iteración.

En mi opinión, la recursividad es más elegante porque parece más declarativa. Es decir, usted establece su algoritmo en términos del resultado que desea en lugar de cómo desea obtener ese resultado.

Personalmente, reflexiono un poco más sobre un problema si estoy tomando el camino de la recursividad. Entonces lo entiendo un poco mejor.

Creo que lo que lo hace más elegante es que generalmente quieres tomar el camino funcional; lo cual es elegante porque tienes menos variables y son inmutables.

Creo que la elegancia (para la recursión misma) viene en el estado mental al que se presta. Dado que tiene que pensar en la solución “hacia atrás y hacia adelante”. Mientras que escribir un bucle se puede hacer casi sin pensar.

Creo que una gran parte de la respuesta es que, en una recursión, generalmente tienes muchas menos declaraciones con efectos secundarios. Todas las variables tienen un valor fijo.