¿Son mejores los lenguajes funcionales en la recursividad?

41

TL; DR: ¿Los lenguajes funcionales manejan la recursividad mejor que los no funcionales?

Actualmente estoy leyendo Code Complete 2. En algún momento del libro, el autor nos advierte sobre la recurrencia. Él dice que debe evitarse cuando sea posible y que las funciones que usan recursividad son generalmente menos efectivas que una solución que usa bucles. Como ejemplo, el autor escribió una función de Java usando la recursión para calcular el factorial de un número como este (puede que no sea exactamente lo mismo ya que no tengo el libro conmigo en este momento):

public int factorial(int x) {
    if (x <= 0)
        return 1;
    else
        return x * factorial(x - 1);
}

Esto se presenta como una mala solución. Sin embargo, en lenguajes funcionales, el uso de la recursión es a menudo la forma preferida de hacer las cosas. Por ejemplo, aquí está la función factorial en Haskell usando recursividad:

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

Y es ampliamente aceptado como una buena solución. Como he visto, Haskell usa la recursión muy a menudo, y no vi en ninguna parte que esté mal visto.

Entonces mi pregunta es básicamente:

  • ¿Los lenguajes funcionales manejan la recursividad mejor que los no funcionales?

EDITAR: Soy consciente de que los ejemplos que utilicé no son los mejores para ilustrar mi pregunta. Solo quería señalar que Haskell (y los lenguajes funcionales en general) usan la recursión con mucha más frecuencia que los lenguajes no funcionales.

marco-fiset
fuente
10
Caso en cuestión: muchos lenguajes funcionales hacen un uso intensivo de la optimización de llamadas de cola, mientras que muy pocos lenguajes de procedimiento lo hacen. Esto significa que la recursividad de llamadas de cola es mucho más barata en esos lenguajes funcionales.
Joachim Sauer
77
En realidad, la definición de Haskell que diste es bastante mala. factorial n = product [1..n]es más sucinto, más eficiente y no desborda la pila en grande n(y si necesita memorización, se requieren opciones completamente diferentes). productse define en términos de algunos fold, que se define de forma recursiva, pero con extremo cuidado. La recursión es una solución aceptable la mayor parte del tiempo, pero aún así es fácil hacerlo mal / subóptimo.
1
@JoachimSauer: con un poco de adorno, su comentario sería una respuesta valiosa.
Mark Booth
Su edición indica que no entendió mi deriva. La definición que dio es un ejemplo perfecto de recursión que es mala incluso en lenguajes funcionales . Mi alternativa también es recursiva (aunque está en una función de biblioteca) y muy eficiente, solo la forma en que se repite hace la diferencia. Haskell también es un caso extraño en el sentido de que la pereza rompe las reglas habituales (ejemplo: las funciones pueden desbordar la pila mientras son recursivas en la cola y ser muy eficientes sin ser recursivas en la cola).
@delnan: ¡Gracias por la aclaración!
Editaré

Respuestas:

36

Sí, lo hacen, pero no solo porque pueden , sino porque tienen que hacerlo .

El concepto clave aquí es la pureza : una función pura es una función sin efectos secundarios y sin estado. Los lenguajes de programación funcional generalmente adoptan la pureza por muchas razones, como razonar sobre el código y evitar dependencias no obvias. Algunos lenguajes, especialmente Haskell, incluso van tan lejos como para permitir solo código puro; cualquier efecto secundario que pueda tener un programa (como realizar E / S) se mueve a un tiempo de ejecución no puro, manteniendo puro el lenguaje.

No tener efectos secundarios significa que no puede tener contadores de bucle (porque un contador de bucle constituiría un estado mutable y modificar dicho estado sería un efecto secundario), por lo que lo más iterativo que puede obtener un lenguaje funcional puro es iterar sobre una lista ( esta operación se llama típicamente foreacho map). Sin embargo, la recursión es una coincidencia natural con la programación funcional pura: no se necesita ningún estado para recurrir, excepto los argumentos de la función (solo lectura) y un valor de retorno (solo escritura).

Sin embargo, no tener efectos secundarios también significa que la recursividad puede implementarse de manera más eficiente, y el compilador puede optimizarla de manera más agresiva. Yo mismo no he estudiado en profundidad ninguno de estos compiladores, pero por lo que puedo ver, la mayoría de los compiladores de lenguajes de programación funcional optimizan las llamadas de cola, y algunos incluso pueden compilar ciertos tipos de construcciones recursivas en bucles detrás de escena.

tdammers
fuente
2
Para el registro, la eliminación de la cola no depende de la pureza.
scarfridge
2
@scarfridge: Por supuesto que no. Sin embargo, cuando la pureza es un hecho, es mucho más fácil para un compilador reordenar su código para permitir llamadas de cola.
tdammers
GCC hace un trabajo de TCO mucho mejor que GHC, porque no puedes hacer TCO a través de la creación de un thunk.
dan_waterworth
18

Estás comparando recursividad versus iteración. Sin la eliminación de llamadas de cola , la iteración es de hecho más eficiente porque no hay una llamada de función adicional. Además, la iteración puede continuar para siempre, mientras que es posible quedarse sin espacio de pila de demasiadas llamadas a funciones.

Sin embargo, la iteración requiere cambiar un contador. Eso significa que debe haber una variable mutable , que está prohibida en un entorno puramente funcional. Por lo tanto, los lenguajes funcionales están especialmente diseñados para operar sin la necesidad de iteración, de ahí las llamadas de función optimizadas.

Pero nada de eso explica por qué su código de muestra es tan elegante. Su ejemplo muestra una propiedad diferente, que es la coincidencia de patrones . Es por eso que la muestra de Haskell no tiene condicionales explícitos. En otras palabras, no es la recurrencia simplificada lo que hace que su código sea pequeño; Es la coincidencia de patrones.

chrisaycock
fuente
¡Ya sé de qué se trata la coincidencia de patrones y creo que es una característica increíble en Haskell que extraño en los idiomas que uso!
marco-fiset
@marcof Mi punto es que todo lo que se habla sobre la recursión frente a la iteración no aborda la elegancia de su muestra de código. Realmente se trata de la coincidencia de patrones vs condicionales. Quizás debería haber puesto eso en primer lugar en mi respuesta.
chrisaycock
Sí, también lo entendí: P
marco-fiset
@chrisaycock: ¿Sería posible ver la iteración como una recursión de cola en la que todas las variables utilizadas en el cuerpo del bucle son argumentos y valores de retorno de las llamadas recursivas?
Giorgio
@Giorgio: Sí, haga que su función tome y devuelva una tupla del mismo tipo.
Ericson2314
5

Técnicamente no, pero prácticamente sí.

La recursión es mucho más común cuando adoptas un enfoque funcional del problema. Como tal, los lenguajes diseñados para usar un enfoque funcional a menudo incluyen características que hacen que la recursión sea más fácil / mejor / menos problemática. Fuera de mi cabeza, hay tres comunes:

  1. Tail Call Optimization. Como lo señalan otros carteles, los lenguajes funcionales a menudo requieren TCO.

  2. Evaluación perezosa. Haskell (y algunos otros idiomas) se evalúa perezosamente. Esto retrasa el "trabajo" real de un método hasta que se requiera. Esto tiende a conducir a estructuras de datos más recursivas y, por extensión, a métodos recursivos para trabajar en ellas.

  3. Inmutabilidad. La mayoría de las cosas con las que trabaja en lenguajes de programación funcionales son inmutables. Esto facilita la recursividad porque no tiene que preocuparse por el estado de los objetos a lo largo del tiempo. Por ejemplo, no puede cambiar un valor debajo de usted. Además, muchos idiomas están diseñados para detectar funciones puras . Dado que las funciones puras no tienen efectos secundarios, el compilador tiene mucha más libertad sobre el orden en que se ejecutan las funciones y otras optimizaciones.

Ninguna de estas cosas es realmente específica de los lenguajes funcionales en comparación con otras, por lo que no son simplemente mejores porque son funcionales. Pero debido a que son funcionales, las decisiones de diseño tomadas tenderán a estas características porque son más útiles (y sus desventajas menos problemáticas) cuando se programa funcionalmente.

Telastyn
fuente
1
Re: 1. Los retornos tempranos no tienen nada que ver con las llamadas de cola. Puede regresar temprano con una llamada de cola, y tener el retorno "tardío" también presenta una llamada de cola, y puede tener una sola expresión simple con la llamada recursiva no en una posición de cola (véase la definición factorial de OP).
@delnan: gracias; es temprano y ha pasado bastante tiempo desde que lo estudié.
Telastyn
1

Haskell y otros lenguajes funcionales generalmente usan evaluación perezosa. Esta característica le permite escribir funciones recursivas sin fin.

Si escribe una función recursiva sin definir un caso base donde termina la recursión, terminará teniendo llamadas infinitas a esa función y stackoverflow.

Haskell también admite optimizaciones de llamadas a funciones recursivas. En Java, cada llamada de función se acumularía y causaría una sobrecarga.

Entonces, sí, los lenguajes funcionales manejan la recursividad mejor que otros.

Mert Akcakaya
fuente
55
Haskell se encuentra entre los pocos idiomas no estrictos: toda la familia de ML (aparte de algunas derivaciones de investigación que agregan pereza), todos los Lisps, Erlang, etc. populares son estrictos. Además, los segundos párrafos parecen estar apagados, como usted dice correctamente en el primer párrafo, la pereza permite la recursión infinita (el preludio de Haskell tiene una inmensa utilidad, forever a = a >> forever apor ejemplo).
@deinan: Hasta donde yo sé, SML / NJ también ofrece una evaluación perezosa, pero es una adición a SML. También quería nombrar dos de los pocos lenguajes funcionales perezosos: Miranda y Clean.
Giorgio
1

La única razón técnica que conozco es que algunos lenguajes funcionales (y algunos lenguajes imperativos si recuerdo) tienen lo que se llama optimización de llamada de cola que permite que un método recursivo no aumente el tamaño de la pila con cada llamada recursiva (es decir, la llamada recursiva más o menos reemplaza la llamada actual en la pila).

Tenga en cuenta que esta optimización no funciona en ninguna llamada recursiva, solo en métodos recursivos de llamada de cola (es decir, métodos que no mantienen el estado en el momento de la llamada recursiva)

Steven Evers
fuente
1
(1) Dicha optimización solo se aplica en casos muy específicos: el ejemplo de OP no son ellos, y muchas otras funciones sencillas necesitan un cuidado adicional para volverse recursivas. (2) La optimización real de las llamadas de cola no solo optimiza las funciones recursivas, sino que elimina la sobrecarga de espacio de cualquier llamada que es seguida inmediatamente por un retorno.
@delnan: (1) Sí, muy cierto. En mi 'proyecto original' de esta respuesta, me había mencionado que :( (2) Sí, pero dentro del contexto de la pregunta, pensé que eso sería ajena a la mención.
Steven Evers
Sí, (2) es solo una adición útil (aunque indispensable para el estilo de paso de continuación), no es necesario mencionar las respuestas.
1

Usted querrá mirar a la recolección de basura es rápido, pero una pila es más rápido , un documento sobre el uso de lo que los programadores de C se le ocurriría como "montón" de los marcos de pila en C compilado Creo que el autor vanamente con gcc para hacer eso . No es una respuesta definitiva, pero eso podría ayudarlo a comprender algunos de los problemas con la recursividad.

El lenguaje de programación Alef , que solía venir junto con el Plan 9 de Bell Labs, tenía una declaración de "convertirse" (consulte la sección 6.6.4 de esta referencia ). Es una especie de optimización de recursión de cola explícita. El "pero usa la pila de llamadas!" El argumento contra la recursividad podría ser eliminado.

Bruce Ediger
fuente
0

TL; DR: Sí.
La recurrencia es una herramienta clave en la programación funcional y, por lo tanto, se ha trabajado mucho para optimizar estas llamadas. Por ejemplo, R5RS requiere (¡en la especificación!) Que todas las implementaciones manejen llamadas de recursión de cola sin consolidar sin que el programador se preocupe por el desbordamiento de la pila. A modo de comparación, de manera predeterminada, el compilador de C no hará ni siquiera una optimización obvia de la cola (intente un reverso recursivo de una lista vinculada) y después de algunas llamadas, el programa terminará (aunque el compilador se optimizará si usa: O2).

Por supuesto, en los programas que están horriblemente escritos, como el famoso fibejemplo que es exponencial, el compilador tiene pocas o ninguna opción para hacer su "magia". Por lo tanto, se debe tener cuidado de no obstaculizar los esfuerzos del compilador en la optimización.

EDITAR: Por el ejemplo de fib, me refiero a lo siguiente:

(define (fib n)
 (if (< n 3) 1 
  (+ (fib (- n 1)) (fib (- n 2)))
 )
)
K.Steff
fuente
0

Los lenguajes funcionales son mejores en dos tipos muy específicos de recursión: recursión de cola y recursión infinita. Son tan malos como otros idiomas en otros tipos de recursión, como su factorialejemplo.

Eso no quiere decir que no haya algoritmos que funcionen bien con recursividad regular en ambos paradigmas. Por ejemplo, cualquier cosa que requiera una estructura de datos similar a una pila de todos modos, como una búsqueda de árbol de profundidad primero, es más simple de implementar con recursividad.

La recursión aparece más a menudo con la programación funcional, pero también se usa en exceso, especialmente por principiantes o en tutoriales para principiantes, tal vez porque la mayoría de los principiantes en programación funcional han usado la recursividad antes en la programación imperativa. Existen otras construcciones de programación funcional, como listas de comprensión, funciones de orden superior y otras operaciones en colecciones, que generalmente son mucho más adecuadas conceptualmente, por estilo, por concisión, por eficiencia y por capacidad de optimización.

Por ejemplo, la sugerencia de delnan factorial n = product [1..n]no solo es más concisa y fácil de leer, sino que también es altamente paralelizable. Lo mismo para usar una foldo reducesi su idioma no tiene una productya incorporada. La recursión es la solución de último recurso para este problema. La razón principal por la que ve que se resuelve de forma recursiva en los tutoriales es como un punto de partida antes de llegar a mejores soluciones, no como un ejemplo de una mejor práctica.

Karl Bielefeldt
fuente