En la clase anterior introdujimos el concepto de recursividad o recursión. En esta clase vamos a consolidarlo, repasando sus fundamentos y haciendo ejercicios para tratar de entenderlo.

En primer lugar, recordemos que de un programa recursivo se espera:

1. puede tratar un número indeterminado de elementos (como en la inducción matemática)
2. termina en algún momento (a diferencia de la inducción matemática)

Para garantizar que se cumplen estos dos requisitos, los programas o funciones recursivos tienen que tener las siguientes tres propiedades:

1. la función se llama a sí misma por lo menos en uno de los casos de su definición (caso(s) recursivo o inductivo),
2. la función NO se llama a sí misma por lo menos en uno de los casos de su definición (caso(s) base), y
3. la condición de aplicación del caso recursivo se modifica cada vez que se aplica éste, de forma que eventualmente no se cumple más la condición y se llega al caso base.

La recursividad funciona para cualquier tipo de estructuras con un número indeterminado de elementos, como por ejemplo los números naturales.

Veamos por ejemplo la función repetir :: Int → a → [a], que dado un elemento lo repite n veces, dando como resultado una lista que contiene las repeticiones. En este caso la recursividad se dá en los naturales desde 0 hasta n. Este número n no lo conocemos a priori, por lo tanto a la hora de escribir el programa no podemos escribir qué hacer en cada uno de los casos desde 0 hasta n, sino que tenemos que usar un mecanismo general que diga qué hacer en un caso cualquiera de esta sucesión. La recursividad nos va a dar el mecanismo para pasar de un caso al siguiente todas las veces que sea necesario, y nosotros vamos a definir en el programa qué hacer al pasar de un caso cualquiera al siguiente. Veamos una posible solución para esta la función:

repetir :: Int -> a -> [a]
repetir 0 x = []
repetir n x = x : repetir (n-1) x

La función potencia :: Int → Int → Int, toma dos enteros x y n, y calcula x^n usando multiplicación y recursividad.

multiplicar :: Int → [Int] → [Int] que dada un número n y una lista, multiplica cada uno de los elementos por n. Ejemplo: multiplicar.3.[3,0,-2] = [9,0,-6].

Definir la función soloPares :: [Int] → [Int] que dada una lista de enteros devuelve una lista que contiene sólo los pares de la lista original. Ejemplo: soloPares [6,5,12,21] = [6,12].

sumatoria

productoria

(el neutro)

Definir la función longitud :: [Int] → Int que dada una lista de enteros computa su largo. Ejemplo: longitud.[3,0,-2] = 3.

Definir la función sumaPares :: [(Int, Int)] → Int, que dada una lista de pares de números, devuelve la sumatoria de todos los números de todos los pares. Ejemplo: sumaPares.[(1,2)(7,8)(11,0)] = 29.

• Definir la función existe :: a → [a] → Bool, que dado un elemento y una lista, devuelve True si el elemento está en la lista. Fíjense que se trata de una generalización del ejercicio anterior.

• Definir la función paratodo :: a → [a] → Bool, que dado un elemento y una lista, devuelve True si todos los elementos de la lista son iguales al elemento que damos como primer argumento.

• Definir la función cuantosCumplen :: (Int → Bool) → [Int] → Int, que dado un predicado p y una lista de enteros xs, cuenta cuántos elementos de la lista cumplen con p.
• Definir la función sumaPares, sumaPares :: [Int] → Int, que suma sólo los elementos pares de una lista.
• Definir la función totalSueldos :: [Int] → Int, que dada una lista con el monto de cada uno de los sueldos que paga una empresa, aplica una suba del 5% a todos los sueldos y devuelve el monto total que gastará la empresa en sueldos.
• Definir la función edadPromedio:: [(String,Int)] → Int, que dada una lista de pares (nombre,edad), retorna el promedio de edad de las personas.