Me encanta

La recursión es una belleza y me encanta, ademas me recuerda que ser flojo no es tan malo. En las definiciones inductivas/recursivas uno "realmente" resuelve un caso y el resto se lo pasa a sus "hijos" u a otros. Definir funciones sobre algunos conjuntos inductivos es sencillo y demostrar algunas cosas sobre ellas suele ser en general sencillo. Por ejemplo a las listas las podemos definir así.

a) [] la lista vacia es una lista
b) (x:xs) un elemento seguido de una lista es una lista
c) son todas

Definir una función sobre listas es sencillo, por ejemplo si queremos definir una función ap que nos diga cuantas veces aparece un elemento x en una lista lo hariamos asi


ap x [] = 0
ap x (y:xs) = if x== y then 1 + (ap x xs) else (ap x xs)


Una vez hecho esto es fácil demostrar algunas propiedades de esta función, por ejemplo, si xs++ys es la lista que resulta de concatenar/pegar las lista xs e ys tenemos:


ap x (xs++ys) = (ap x xs)+ (ap x ys)


Esta propiedad es bastante obvia, pero dar una prueba formal de ella ayuda a dar un ejemplo del porque las matemáticas son la principal herrmienta de las ciencias de la computación.

La demostración sería usando inducción estructural


Caso base xs=[]
Hipotesis de inducción xs = ys
Paso inductivo xs =(z:zs)


Otro ejemplo bello de la recursión es el siguiente


quicksort [] =[]
quicksort (x:xs) =
quicksort [y| y <- xs, y <= x] ++ [x] ++ quicksort [z| z <- xs, x < z]


Que también es un bonito ejemplo de prgramación funcional. Por esta y muchas otras razones me encanta la recursión... amo ser flojo "a la buena".

P.D para entender la recusión primero hay que entender la recursión...