I1M2012: Definiciones por recursión (3)
En la primera parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos concluido el estudio de las definiciones por recursión en Haskell. Concretamente, hemos visto ejemplos de recursión recursión múltiple y de recursión mutua. También hemos comentado el método para construir funciones recursivas.
En la segunda parte hemos comentado la solución del problema 4 (último dígito del producto de números de Fermat).
Las transparencias usadas en la clase son las comprendidas entre las páginas 14 y 24 del tema 6:
El código correspondiente es
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
-- --------------------------------------------------------------------- -- Recursión múltiple -- -- --------------------------------------------------------------------- -- (ordena xs) es la lista obtenida ordenando xs meciante el algoritmo -- de ordenación rápida. Por ejemplo, -- ordena [2,5,4,7] == [2,4,5,7] ordena :: (Ord a) => [a] -> [a] ordena [] = [] ordena (x:xs) = (ordena menores) ++ [x] ++ (ordena mayores) where menores = [a | a <- xs, a <= x] mayores = [b | b <- xs, b > x] -- --------------------------------------------------------------------- -- Recursión mutua -- -- --------------------------------------------------------------------- -- (par x) se verifica si x es par e (impar x) se verifica si x es -- impar. Por ejemplo, -- par 3 == False -- impar 3 == True par :: Int -> Bool par 0 = True par (n+1) = impar n impar :: Int -> Bool impar 0 = False impar (n+1) = par n -- (pares xs) son los elementos de xs que ocupan posiciones pares e -- (impares xs) son los elementos de xs que ocupan posiciones -- impares. Por ejemplo, -- pares [1,3,5,7] == [1,5] pares :: [a] -> [a] pares [] = [] pares (x:xs) = x : impares xs impares :: [a] -> [a] impares [] = [] impares (_:xs) = pares xs -- --------------------------------------------------------------------- -- Heurísticas para las definiciones recursivas -- -- --------------------------------------------------------------------- -- (init xs) es la lista xs sin el último elemento. Por ejemplo, -- init [3,2,5] == [2,5] init :: [a] -> [a] init [_] = [] init (x:xs) = x : init xs |