25 feb. 2009

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...

3 comentarios:

ender dijo...

Buen post! También me considero fan de la recursión aunque mi fuerte no sean los lenguajes funcionales.

Hay veces que me arrepiento de mi formación como ingeniero. Sin embargo, luego recuerdo dos o tres cosas que valieron la pena del trayecto y mi mente viaja a otra idea.

Shy Guy dijo...

Amén!!!

Recuerdo con emoción la primera vez que me mostraron su poder con el clásico ejemplo de la función factorial, y después al definir listas y árboles. Fue así como "orale, nunca imaginé que en matemáticas existiesen cosas así".

Más que las epsilons y deltas, creo que la recursión fué lo que más me atrapó en mis inicios en nuestra querida Fac. de Ciencias.

Saludos.

Eduardo Pacheco (PAGE) dijo...

Lo curioso es que a mis inicios en la facultad Elisa nos decia que pensar recursivamente era "natural" y a mi no se me hacia tan natural, pensar de manera "no recursiva" era mas facil... según el yo de esos tiempos. Para cuando estaba al final de la carrera pensar de forma "no recursiva" era algo muy dificil... y recursivamente era natural.... y sí, me gusta más la recursíon que las epsilon y deltas!!!

ga