====== Clase 3 ======
===== Recursividad, caso base y caso inductivo =====
Hasta este momento habíamos visto funciones que llamaban a otras funciones, como por ejemplo //ordenaSiPositivos//, que llamaba a //ambosPositivos// para saber si los números con los que estaba tratando eran positivos o no. Ahora veremos funciones que se llaman a sí mismas, lo cual es un mecanismo muy fuerte y bien conocido llamado [[http://es.wikipedia.org/wiki/Recursi%C3%B3n|recursividad, recurrencia o recursión]].
La recursividad es una forma de definir funciones de manera tal que la función se contiene a sí misma en su propia definición. En informática añadimos un requisito más a las funciones recursivas: exigimos a una función recursiva **termine**. Puede suceder que una función recursiva mal definida no termine nunca, sino que caiga en lo que llamamos un **[[http://en.wikipedia.org/wiki/Infinite_loop|bucle infinito]]**. Por ejemplo, la siguiente función:
sucesion :: Int -> [Int]
sucesion n | n > 0 = n : sucesion (n+1)
| n <= 0 = sucesion 1
En esta función, si //n// es positivo, se va a aplicar la función //sucesion//, con el efecto de concatenar //n// y aplicar la función //sucesion// con //(n+1)// como argumento. Evidentemente, //(n+1)// también será positivo, así que la función se aplicará infinitamente. Si //n// es negativo o 0, se aplicará //sucesion 1//, como 1 es positivo, entraremos en el mismo bucle que veíamos en el caso anterior.
Para evitar que eso suceda, las funciones recursivas tienen dos partes: el/los caso/s base y el caso recursivo. El **caso base** es el que evita que nos metamos en un bucle infinito, es el caso que hace parar la recursión ya que no llama a la función. El **caso recursivo** es aquél en el que una función se llama a sí misma, y es el que hace que la recursión continúe hasta que se encuentre con el caso base.
Tanto el caso recursivo como el caso base tienen condiciones de aplicación, que son justamente los **//casos//** (que normalmente obtenemos después de un análisis por casos del problema a solucionar). Para evitar meternos en un bucle infinito, es importante que el caso recursivo modifique su condición de aplicación, si no, mientras la condición del caso recursivo sea válida, seguirá aplicándose... infinitamente! Veamos un ejemplo parecido al anterior donde sí se modifica la condición de aplicación de forma que se llegue a algún punto en el que no se pueda aplicar más.
sucesionInversa :: Int -> [Int]
sucesionInversa n | 0<=n = n : sucesionInversa (n-1)
| n<0 = []
En esta función, si //n// es negativo, se corta la recursividad, y además, para cualquier valor de //n//, sabemos que en algún momento vamos a llegar a un valor negativo, ya que en cada aplicación del paso recursivo se decrementa el valor de n.
==== Definición de factorial ====
Veamos el ejemplo más conocido, la función //factorial//:
factorial :: Int -> Int
factorial 0 = 1 -- caso base
factorial (n+1) = (n+1) * factorial n -- caso inductivo
En esta función, el caso base se da cuando //n==0//; en ese caso no se llama a la función misma si no que se realiza una acción y se termina. En cambio, mientras //n>0// se aplica la función y se vuelve a llamar a sí misma. Notemos que la condición de aplicación del caso recursivo se va modificando, es decir, //n// se va modificando de forma que en algún momento llegará a ser 0 y ahí se aplicará el caso base. Eso nos garantiza que el programa terminará y no nos meteremos en un bucle infinito.
Veamos cómo funciona //factorial// para el número 3:
factorial 3
= {factorial n = n * factorial (n-1)}
3 * factorial (3-1)
= {álgebra}
3 * factorial (2)
= {factorial n = n * factorial (n-1)}
3 * 2 * factorial (2-1)
= {álgebra}
3 * 2 * factorial (1)
= {factorial n = n * factorial (n-1)}
3 * 2 * 1 * factorial (1-1)
= {álgebra}
3 * 2 * 1 * factorial (0)
= {factorial 0 = 1}
3 * 2 * 1 * 1
= {álgebra}
6
==== Definición de Sucesión de Fibonacci ====
Otros ejemplo célebre de recursión con números es la [[http://es.wikipedia.org/wiki/Sucesi%C3%B3n_de_Fibonacci|Sucesión de Fibonacci]].
fib (n+2) = fib (n+1) + fib n
Una particularidad de la Sucesión de Fibonacci es que es **doblemente recursiva**, ya que se llama dos veces a sí misma en cada paso, y no tiene un caso base, sino dos: fib 0 = 0 y fib 1 = 1.
===== Recursividad en listas =====
La recursivdad, junto con el //pattern matching// que vimos en la clase anterior, nos ofrece una forma muy natural de recorrer listas. El caso base suele ser la lista vacía ''[]'', y el caso inductivo suele ser la lista con uno o más elementos ''(x:xs)''. El caso inductivo modifica su condición de aplicación eliminando elementos de la lista, de forma que en algún momento la lista queda vacía, con lo que se llega al caso base y el programa termina. Para separar la parte de la lista que ya se ha procesado de la parte que queda por procesar, se usa pattern matching: se distingue la cabeza de la lista, a la que habitualmente se aplica alguna operación, y la cola, a la que se aplica la función de vuelta. Notemos que la cola es la misma lista original pero con un elemento menos, justamente, la cabeza. Veamos un ejemplo, la función //negarTodos//, que, dada una lista, nos devuelve la misma lista:
negarTodos :: [Bool] -> [Bool]
negarTodos [] = [] -- caso base
negarTodos (x:xs) = not x : negarTodos xs -- caso inductivo
Veamos cómo se aplica la función //negarTodos// a la lista [1,2,3]:
negarTodos [True,False,False,False,True]
= {negarTodos (x:xs)}
not True : negarTodos [False,False,False,True]
= {negarTodos (x:xs)}
not True : not False : negarTodos [False,False,True]
= {negarTodos (x:xs)}
not True : not False : not False : negarTodos [False,True]
= {negarTodos (x:xs)}
not True : not False : not False : not False : negarTodos [True]
= {negarTodos (x:xs)}
not True : not False : not False : not False : not True : negarTodos []
= {negarTodos []}
not True : not False : not False : not False : not True : []
= {lógica}
False : True : True : True : True : []
= {definición de []}
[False,True,True,True,False]
==== Aplicar (Map) ====
Veamos ahora otro ejemplo, con la función //duplicar.xs//, //duplicar :: [Int] -> [Int]// que dada una lista multiplica por 2 cada uno de sus elementos (ej.: //duplicar [2,4,8] = [4,8,16]//).
Veamos varias formas en que la función estaría **MAL** definida:
duplicar :: [Int] -> [Int]
duplicar [] = []
duplicar (x:xs) = 2*x : xs
Probamos la función y obtenemos
Main> duplicar []
[]
Main> duplicar [10]
[20]
Main> duplicar [10,20]
[20,20]
Main> duplicar [10,20,30]
[20,20,30]
En este caso, la función **no se llama a sí misma**, así que sólo se aplicaría a la cabeza de la lista, y no a todo el resto.
Corregimos este error.
duplicar :: [Int] -> [Int]
duplicar [] = []
duplicar (x:xs) = 2*x : duplicar (x:xs)
Probamos de nuevo la definición y obtenemos
Main> duplicar []
[]
Main> duplicar [10]
[20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20 ...
En este caso, el caso recursivo no modifica su condición de aplicación, así que nunca va a llegar al caso base y por lo tanto caerá en un bucle infinito.
La función //duplicar.xs// estaría bien definida de la siguiente forma:
duplicar :: [Int] -> [Int]
duplicar [] = [] -- caso base
duplicar (x:xs) = 2*x : duplicar xs -- caso inductivo
La probamos.
Main> duplicar [10,20]
[20,40]
Main> duplicar [10,20,30]
[20,40,60]
Main> duplicar [1..10]
[2,4,6,8,10,12,14,16,18,20]
Main> duplicar [0..10]
[0,2,4,6,8,10,12,14,16,18,20]
Notar que en las funciones de tipo "map" toman siempre a una lista como argumento y devuelven una lista como resultado; la lista de resultado se obtiene de **concatenar** el resultado de aplicar una función dada a cada uno de los elementos de la lista argumento.
==== Acumular (Fold) ====
Veamos la función //sumatoria.xs//, //sumatoria : [Int] -> Int//, que dada una lista devuelve la suma de sus elementos.
sumatoria :: [Int] -> Int
sumatoria [] = 0
sumatoria (x:xs) = x + sumatoria xs
Notar que en las funciones de tipo "fold" toman una lista como argumento. El resultado se obtiene de **acumular** los resultados de aplicar una función dada a cada uno de los elementos de la lista argumento. La forma en como se acumulan los resultados depende de cada función: en la función //sumatoria// se suman, en la función //productoria// se multiplican, etc.
Probamos en algunos valores de entrada.
Main> sumatoria []
0
Main> sumatoria [0]
0
Main> sumatoria [0,0]
0
Main> sumatoria [1..3]
6
Main> sumatoria [1..10]
55
Main> sumatoria [1..10000]
50005000
==== Seleccionar (Filter) ====
Veamos la función //empiezaM.xs//, //empiezaM : [String] -> [String]// que dada una lista de nombres (representados como //String// o //[Char]//, que son tipos equivalentes) nos devuelve todos aquellos nombres que empiezan con la letra "m".
empiezaM :: [String] -> [String]
empiezaM [] = []
empiezaM (x:xs) | cabeza x == 'm' = x : empiezaM xs
| otherwise = empiezaM xs
Notar que en las funciones de tipo "filter" toman una lista como argumento y devuelven una lista como resultado. La lista de resultado se obtiene de concatenar los elementos de la lista de argumento que devuelven un valor especificado para una función dada (típicamente, los elementos que devuelven True para un predicado).
Veamos como funciona.
Main> empiezaM ["marta", "liliana", "esther", "mario"]
["marta","mario"]
Main> empiezaM ["Merceditas", "Tabaré"]
[]
==== Múltiples casos base ====
Recordemos que el número de casos base depende del problema concreto que estemos tratando. En la Sucesión de Fibonacci, encontramos dos casos base: fib 0 = 1 y fib 1 = 1. En la mayor parte de casos con listas tenemos un solo caso base, el de la lista vacía [], pero para algunos problemas podemos necesitar 2 o más casos base. Veamos por ejemplo la función //emparejar.xs//, //emparejar : [String] -> [(String,String)]//, que pone en parejas los elementos de una lista de strings que representen, por ejemplo, los nombres de los chicos de una clase, y nos devuelve una forma de agruparlos en parejas para, por ejemplo, distribuirlos en los asientos de un colectivo.
emparejar :: [String] -> [(String,String)]
emparejar (x:y:xs) = (x,y) : emparejar xs
emparejar [x] = [(x,x)]
emparejar [] = []
Veamos cómo funciona.
Main> emparejar ["Pepa","Lola","Juan","Pili","Pedro"]
[("Pepa","Lola"),("Juan","Pili"),("Pedro","Pedro")]
===== Ejercicios =====
=== Aplicar ===
* Definir la función //veintePorCiento.xs//, //veintePorCiento : [Float] -> [Float]// que dada una lista de números devuelve una lista con el 20% de cada elemento de la lista.
probar con [345,20,46,0], [] y [3].
* Generalizar la función //veintePorCiento// definiendo //porCiento.n.xs//, //porCiento : Int -> [Float] -> [Float]// que dado un número //n// y una lista, devuelve el //n// por ciento de cada uno de los elementos de la lista. Ejemplo: //porCiento 10 [200,87,6] = [20,8.7,0.6]//. Puede ser útil la función ''fromIntegral'' que transforma un ''Int'' en ''Float''.
* Generalizar la función //duplicar// definiendo //multiplicar.n.xs//, //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]//.
probar con 1 [3,2,1], 10 [3,2,1], 0 [0,1,2] y [] 3.
=== Acumular ===
* Definir la función //productoria.xs//, //productoria : [Int] -> Int// que dada una lista devuelve el producto de sus elementos.
probar con [1,2,3,4], [0,1,2,3,4], [0], [3,2,1], [3,2,1,1], [3,2,1,1,1], [3,2,1,1,1,1], [-8,3,2], [].
* Definir la función //longitud.xs//, //longitud : [Int] -> Int// que dada una lista de enteros computa su largo. Ejemplo: //longitud.[3,0,-2] = 3//.
probar con [3,2,1], con [0,1,2] y con [].
=== Filtrar ===
* Definir la función //soloPares.xs//, //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]//.
probar con [2,4,6,8], [0,1,2,3], [0,1], [1] y [].
* Definir la función //ningunFalse.xs//, //ningunFalse : [Bool] -> [Bool]// que dada una lista de booleanos devuelve una lista sin ningún booleano False. Ejemplo //ningunFalse [False,True,False,True] = [True,True]//.
probar con [False], [True], [True,False,True], [False,True,False], [].
=== Miscelánea ===
* Escribir la función que calcula la Sucesión de Fibonacci, //fib.n//, //fib : Int -> Int//, que se define así: //fib (n+2) = fib (n+1) + fib n//.
probar con 4, 3, 2, 1 y 0.
* Definir la función //sumaPares.xs//, //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//. (ejemplo 2.16 del problemario de Pepe Gallardo).
probar con [(1,1)], [] y [(2,1),(1,2)].
* Definir la función //todos0y1.xs//, //todos0y1 : [Int] -> Bool// que dada una lista devuelve //True// si ésta consiste sólo de 0s y 1s. Ayuda: para construir el Booleano del resultado no pueden usar el constructor de listas ":", sino que tienen que usar algún operador que dé como resultado un Booleano.
probar con [0], [], [1], [0,0,0,0], [0,1,0,1], [1,2,3], ['a','b','c']
* Definir la función //hay0.xs//, //hay0 : [Int] -> Bool// que dada una lista //xs// devuelve //True// si ésta contiene algún 0. Ejemplo //hay0.[1,2] = False//, //hay0.[1,4,0,5] = True//.
probar con [], [0,0,0,0], [1,2,3,4], [0] y [1,5,7,0,9]
* Definir la función //repetir.n.x//, //repetir : Int -> a -> [a]// que dado un elemento lo repite n veces, dando como resultado una lista que contiene las repeticiones.
probar con 8 y "bobo", 0 y 33 y 4 y [].
* Definir la función //esMultiploLista.n.xs//, //esMultiploLista : Int -> [Int] -> [Bool]// que dado un entero //n// y una lista de enteros //xs// devuelve una lista de booleanos que indica si //n// es múltiplo de cada uno de los elementos de la lista //xs//. Ejemplo: //esMultiploLista.6.[2,3,5] = [True,True,False]//. Otro ejemplo: //esMultiploLista.18.[4,2,3,6,8] = [False,True,True,True,False]//.