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

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

Otros ejemplo célebre de recursión con números es la 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.

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]

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.

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

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é"]
[]

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")]

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

• 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 [].

• 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], [].

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