{"id":4528,"date":"2014-10-29T18:59:15","date_gmt":"2014-10-29T17:59:15","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4528"},"modified":"2014-10-30T09:03:48","modified_gmt":"2014-10-30T08:03:48","slug":"i1m2014-definiciones-por-recursion","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-definiciones-por-recursion\/","title":{"rendered":"I1M2014:  Definiciones por recursi\u00f3n"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se ha explicado las definiciones por recursi\u00f3n en Haskell. Concretamente, hemos visto ejemplos de<\/p>\n<ul>\n<li>recursi\u00f3n sobre los n\u00fameros naturales,<\/li>\n<li>recursi\u00f3n sobre listas,<\/li>\n<li>recursi\u00f3n sobre varios argumento,<\/li>\n<li>recursi\u00f3n m\u00faltiple y<\/li>\n<li>de recursi\u00f3n mutua.<\/li>\n<\/ul>\n<p>Tambi\u00e9n se ha comentado el m\u00e9todo de 5 pasos para construir funciones recursivas.<\/p>\n<p>El c\u00f3digo correspondiente es<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Recursi\u00f3n num\u00e9rica                                                 --\n-- ---------------------------------------------------------------------\n\n-- (factorial n) es el factorial de n. Por ejemplo,\n--    factorial 3  ==  6\nfactorial :: Integer -> Integer\nfactorial 0     = 1\nfactorial (n+1) = (n+1) * factorial n\n\n-- (m `por` n) es el producto de m por n. Por ejemplo,\n--    3 `por` 2  ==  6\npor :: Int -> Int -> Int\nm `por` 0       = 0\nm `por` (n + 1) = m + (m `por` n)\n\n-- ---------------------------------------------------------------------\n-- Recusi\u00f3n sobre lista                                               --\n-- ---------------------------------------------------------------------\n\n-- (producto xs) es el producto de los n\u00fameros de xs. Por ejemplo,\n--    producto [7,5,2] == 70\nproducto :: Num a => [a] -> a\nproducto []     = 1\nproducto (n:ns) = n * producto ns\n\n-- (longitud xs) es el n\u00famero de elementos de xs. Por ejemplo,\n--    longitud [2,4,5] == 3\nlongitud :: [a] -> Int\nlongitud []     = 0\nlongitud (_:xs) = 1 + longitud xs\n\n-- (inversa xs) es la inversa de xs. Por ejemplo,\n--    inversa [2,5,3]  ==  [3,5,2]  \ninversa :: [a] -> [a]\ninversa []     = []\ninversa (x:xs) = inversa xs ++ [x]\n\n-- (conc xs ys) es la concatenaci\u00f3n de xs e ys. Por ejemplo,\n--    conc [2,5] [3,5,6]  ==  [2,5,3,5,6]\nconc :: [a] -> [a] -> [a]\nconc []     ys = ys\nconc (x:xs) ys = x : conc xs ys\n\n-- (inserta e xs) inserta el elemento e en la lista xs delante del\n-- primer elemento de xs mayor o igual que e. Por ejemplo,\n--    inserta 5 [2,4,7,3,6,8,10] == [2,4,5,7,3,6,8,10]  \ninserta :: Ord a => a -> [a] -> [a]\ninserta e []                  = [e]\ninserta e (x:xs) | e <= x     = e : (x:xs) \n                 | otherwise  = x : inserta e xs    \n\n-- (ordena_por_insercion xs) es la lista xs ordenada mediante inserci\u00f3n,\n-- Por ejemplo, \n--    ordena_por_insercion [2,4,3,6,3] == [2,3,3,4,6]  \nordena_por_insercion :: Ord a => [a] -> [a]\nordena_por_insercion []     = []\nordena_por_insercion (x:xs) = \n    inserta x (ordena_por_insercion xs)   \n\n-- ---------------------------------------------------------------------\n-- Recursi\u00f3n sobre varios argumentos                                  --\n-- ---------------------------------------------------------------------\n\n-- (zip xs ys) es la lista de los pares de los elementos de xs e ys en\n-- la misma posici\u00f3n. Por ejemplo,\n--    zip [1,3,5] [2,4,6,8]  ==  [(1,2),(3,4),(5,6)]\nzip :: [a] -> [b] -> [(a, b)]\nzip []     _      = []\nzip _      []     = []\nzip (x:xs) (y:ys) = (x,y) : zip xs ys\n\n-- (drop n xs) es la lista obtenida eliminando los n primeros elementos\n-- de xs. Por ejemplo,\n--    drop 2 [5,7,9,4] == [9,4]\n--    drop 5 [1,4]     ==  [] \ndrop :: Int -> [a] -> [a]\ndrop 0 xs         = xs\ndrop (n+1) []     = []\ndrop (n+1) (x:xs) = drop n xs\n\n-- ---------------------------------------------------------------------\n-- Recursi\u00f3n m\u00faltiple                                                 --\n-- ---------------------------------------------------------------------\n\n-- (fibonacci n) es el n--\u00e9simo t\u00e9rmino de la sucesi\u00f3n de Fibonacci. Por\n-- ejemplo, \n--    fibonacci 8  ==  21  \nfibonacci :: Int -> Int\nfibonacci 0     = 0\nfibonacci 1     = 1\nfibonacci (n+2) = fibonacci n + fibonacci (n+1)\n\n-- ---------------------------------------------------------------------\n-- Recursi\u00f3n m\u00faltiple                                                 --\n-- ---------------------------------------------------------------------\n\n-- (ordena xs) es la lista obtenida ordenando xs meciante el algoritmo\n-- de ordenaci\u00f3n r\u00e1pida. Por ejemplo,\n--    ordena [2,5,4,7]  ==  [2,4,5,7]\nordena :: (Ord a) => [a] -> [a]\nordena [] = []\nordena (x:xs) = \n    (ordena menores) ++ [x] ++ (ordena mayores)\n    where menores = [a | a <- xs, a <= x]\n          mayores = [b | b <- xs, b > x]\n\n-- ---------------------------------------------------------------------\n-- Recursi\u00f3n mutua                                                    --\n-- ---------------------------------------------------------------------\n\n-- (par x) se verifica si x es par e (impar x) se verifica si x es\n-- impar. Por ejemplo,\n--    par 3    ==  False\n--    impar 3  ==  True\npar :: Int -> Bool\npar 0     = True\npar (n+1) = impar n\n\nimpar :: Int -> Bool\nimpar 0      = False\nimpar (n+1)  = par n\n\n-- (pares xs) son los elementos de xs que ocupan posiciones pares e\n-- (impares xs) son los elementos de xs que ocupan posiciones\n-- impares. Por ejemplo,\n--    pares [1,3,5,7]  ==  [1,5]  \npares :: [a] -> [a]\npares []     = []\npares (x:xs) = x : impares xs\n\nimpares :: [a] -> [a]\nimpares []     = []\nimpares (_:xs) = pares xs\n\n-- ---------------------------------------------------------------------\n-- Heur\u00edsticas para las definiciones recursivas                       --\n-- ---------------------------------------------------------------------\n\n-- (init xs) es la lista xs sin el \u00faltimo elemento. Por ejemplo,\n--    init [3,2,5]  ==  [2,5] \ninit :: [a] -> [a]\ninit [_]    = []\ninit (x:xs) = x : init xs\n<\/pre>\n<p>Las transparencias usadas en la clase son las del <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\/temas\/tema-6t.pdf\">tema 6<\/a><br \/>\n<!--more--><br \/>\n<div class=\"jetpack-video-wrapper\"><iframe src='https:\/\/www.slideshare.net\/slideshow\/embed_code\/5667945' width='1290' height='1057' sandbox=\"allow-popups allow-scripts allow-same-origin allow-presentation\" allowfullscreen webkitallowfullscreen mozallowfullscreen><\/iframe><\/div><\/p>\n<p>Como tarea se ha propuesto escribir de manera colaborativa las soluciones de los ejercicios de la <a href=\"http:\/\/bit.ly\/1wGWHgM\">5\u00ba relaci\u00f3n<\/a> y los ejercicios que diariamente se ir\u00e1n proponiendo en <a href=\"https:\/\/www.glc.us.es\/~jalonso\/exercitium\">Exercitium<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se ha explicado las definiciones por recursi\u00f3n en Haskell. Concretamente, hemos visto ejemplos de recursi\u00f3n sobre los n\u00fameros naturales, recursi\u00f3n sobre listas, recursi\u00f3n sobre varios argumento, recursi\u00f3n m\u00faltiple y de recursi\u00f3n mutua. Tambi\u00e9n se ha comentado el m\u00e9todo de 5 pasos para&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[238],"tags":[270,305],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4528"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=4528"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4528\/revisions"}],"predecessor-version":[{"id":4532,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4528\/revisions\/4532"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4528"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4528"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4528"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}