I1M2014: Definiciones por recursión
En la clase de hoy de Informática de 1º del Grado en Matemáticas se ha explicado las definiciones por recursión en Haskell. Concretamente, hemos visto ejemplos de
- recursión sobre los números naturales,
- recursión sobre listas,
- recursión sobre varios argumento,
- recursión múltiple y
- de recursión mutua.
También se ha comentado el método de 5 pasos para construir funciones recursivas.
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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 |
-- --------------------------------------------------------------------- -- Recursión numérica -- -- --------------------------------------------------------------------- -- (factorial n) es el factorial de n. Por ejemplo, -- factorial 3 == 6 factorial :: Integer -> Integer factorial 0 = 1 factorial (n+1) = (n+1) * factorial n -- (m `por` n) es el producto de m por n. Por ejemplo, -- 3 `por` 2 == 6 por :: Int -> Int -> Int m `por` 0 = 0 m `por` (n + 1) = m + (m `por` n) -- --------------------------------------------------------------------- -- Recusión sobre lista -- -- --------------------------------------------------------------------- -- (producto xs) es el producto de los números de xs. Por ejemplo, -- producto [7,5,2] == 70 producto :: Num a => [a] -> a producto [] = 1 producto (n:ns) = n * producto ns -- (longitud xs) es el número de elementos de xs. Por ejemplo, -- longitud [2,4,5] == 3 longitud :: [a] -> Int longitud [] = 0 longitud (_:xs) = 1 + longitud xs -- (inversa xs) es la inversa de xs. Por ejemplo, -- inversa [2,5,3] == [3,5,2] inversa :: [a] -> [a] inversa [] = [] inversa (x:xs) = inversa xs ++ [x] -- (conc xs ys) es la concatenación de xs e ys. Por ejemplo, -- conc [2,5] [3,5,6] == [2,5,3,5,6] conc :: [a] -> [a] -> [a] conc [] ys = ys conc (x:xs) ys = x : conc xs ys -- (inserta e xs) inserta el elemento e en la lista xs delante del -- primer elemento de xs mayor o igual que e. Por ejemplo, -- inserta 5 [2,4,7,3,6,8,10] == [2,4,5,7,3,6,8,10] inserta :: Ord a => a -> [a] -> [a] inserta e [] = [e] inserta e (x:xs) | e <= x = e : (x:xs) | otherwise = x : inserta e xs -- (ordena_por_insercion xs) es la lista xs ordenada mediante inserción, -- Por ejemplo, -- ordena_por_insercion [2,4,3,6,3] == [2,3,3,4,6] ordena_por_insercion :: Ord a => [a] -> [a] ordena_por_insercion [] = [] ordena_por_insercion (x:xs) = inserta x (ordena_por_insercion xs) -- --------------------------------------------------------------------- -- Recursión sobre varios argumentos -- -- --------------------------------------------------------------------- -- (zip xs ys) es la lista de los pares de los elementos de xs e ys en -- la misma posición. Por ejemplo, -- zip [1,3,5] [2,4,6,8] == [(1,2),(3,4),(5,6)] zip :: [a] -> [b] -> [(a, b)] zip [] _ = [] zip _ [] = [] zip (x:xs) (y:ys) = (x,y) : zip xs ys -- (drop n xs) es la lista obtenida eliminando los n primeros elementos -- de xs. Por ejemplo, -- drop 2 [5,7,9,4] == [9,4] -- drop 5 [1,4] == [] drop :: Int -> [a] -> [a] drop 0 xs = xs drop (n+1) [] = [] drop (n+1) (x:xs) = drop n xs -- --------------------------------------------------------------------- -- Recursión múltiple -- -- --------------------------------------------------------------------- -- (fibonacci n) es el n--ésimo término de la sucesión de Fibonacci. Por -- ejemplo, -- fibonacci 8 == 21 fibonacci :: Int -> Int fibonacci 0 = 0 fibonacci 1 = 1 fibonacci (n+2) = fibonacci n + fibonacci (n+1) -- --------------------------------------------------------------------- -- 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 |
Las transparencias usadas en la clase son las del tema 6
Como tarea se ha propuesto escribir de manera colaborativa las soluciones de los ejercicios de la 5º relación y los ejercicios que diariamente se irán proponiendo en Exercitium.