En esta relaci\u00f3n de ejercicios se muestra c\u00f3mo se pueden transformar programas iterativos (con bucles while o for) en programas en recursivos. Para cada uno de los bucles, se elige una funci\u00f3n y se pide definirla usando el bucle (en Python), buscar una definici\u00f3n recursiva que sea semejante a la anterior, definir el patr\u00f3n que abstrae el bucle, definirla con el patr\u00f3n y aplicar el patr\u00f3n a otras funciones. Finalmente, se estudia c\u00f3mo definir algunas de las anteriores funciones usando el menor punto fijo.<\/p>\n
<\/p>\n
La relaci\u00f3n est\u00e1 elaborado como complemento del tema Funciones de orden superior<\/a> del curso de Inform\u00e1tica<\/a> de primero del Grado en Matem\u00e1ticas.<\/p>\n Nota [Parte impar].<\/strong> Todo n\u00famero entero Ejercicio 1 [Parte impar con while en Python].<\/strong> Definir en Python, usando un blucle while, la funci\u00f3n Soluci\u00f3n:<\/em><\/p>\n Soluci\u00f3n:<\/em><\/p>\n Soluci\u00f3n:<\/em><\/p>\n Ejercicio 4 [Parte impar con el bucle while1].<\/strong> Redefinir, usando Soluci\u00f3n:<\/em><\/p>\n Nota [La \u00f3rbita de Collatz].<\/strong> El sucesor de Collatz de un n\u00famero Soluci\u00f3n:<\/em><\/p>\n Soluci\u00f3n:<\/em><\/p>\n Soluci\u00f3n:<\/em><\/p>\n Soluci\u00f3n:<\/em><\/p>\n Soluci\u00f3n:<\/em><\/p>\n Soluci\u00f3n:<\/em><\/p>\n que traduzca la definici\u00f3n anterior.<\/p>\n Soluci\u00f3n:<\/em><\/p>\n El procedimiento de evaluaci\u00f3n de Soluci\u00f3n:<\/em><\/p>\n Ejercicio 13 [Suma impares con while2].<\/strong> Redefinir, usando Soluci\u00f3n:<\/em><\/p>\n Ejercicio 14 [El algoritmo de Euclides con while en Python].<\/strong> Definir en Python la funci\u00f3n Soluci\u00f3n:<\/em><\/p>\n tal que Soluci\u00f3n:<\/em><\/p>\n Ejercicio 16 [El algoritmo de Euclides con while2].<\/strong> Redefinir, usando Soluci\u00f3n:<\/em><\/p>\n Soluci\u00f3n:<\/em><\/p>\n Soluci\u00f3n:<\/em><\/p>\n Ejercicio 19 [El factorial con while2].<\/strong> Redefinir, con Soluci\u00f3n:<\/em><\/p>\n Soluci\u00f3n:<\/em><\/p>\nEl bucle while con un par\u00e1metro<\/h2>\n
n<\/code> se puede escribir como m*2^k<\/code>, con m<\/code> impar. Se dice que m<\/code> es la parte impar de n<\/code>. Por ejemplo, la parte impar de 40 es 5 porque 40 = 5*2^3.<\/p>\nparteImpar<\/code> tal que parteImpar(n)<\/code> es la parte impar de n<\/code>.<\/p>\n\ndef parteImpar(n): \n while n % 2 == 0:\n n = n\/2\n return n\n<\/pre>\n
\n
parteImpar :: Int -> Int<\/code>\n<\/dd>\n(parteImpar n)<\/code> es la parte impar de n<\/code>. Por ejemplo,<\/dt>\nparteImpar 40 == 5<\/code>\n<\/dd>\n<\/dl>\n\nparteImpar :: Int -> Int\nparteImpar n | even n = parteImpar (n `div` 2)\n | otherwise = n\n<\/pre>\n
\n
while1 :: (a -> Bool) -> (a -> a) -> a -> a<\/code>\n<\/dd>\n(while1 p f x)<\/code> es el resultado de aplicar la funci\u00f3n f<\/code> a x<\/code> mientras cumple la propiedad p<\/code>. Por ejemplo,<\/dt>\nwhile1 (<1000) (*2) 1 == 1024<\/code>\n<\/dd>\n<\/dl>\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n):\nwhile1 :: (a -> Bool) -> (a -> a) -> a -> a\nwhile1 p f x | p x = while1 p f (f x)\n | otherwise = x\n\n-- 2\u00aa definici\u00f3n (con until):\nwhile1b :: (a -> Bool) -> (a -> a) -> a -> a\nwhile1b p f x = until (not . p) f x\n\n-- 3\u00aa definici\u00f3n (con until y composici\u00f3n):\nwhile1c :: (a -> Bool) -> (a -> a) -> a -> a\nwhile1c = until . (not.)\n<\/pre>\n
while1<\/code>, la funci\u00f3n parteImpar<\/code>.<\/p>\n\nparteImpar2 :: Int -> Int\nparteImpar2 = while1 even (`div` 2)\n<\/pre>\n
n<\/code> es n\/2<\/code>, si n<\/code> es par y 3n+1<\/code> , en caso contrario. La \u00f3rbita de un n\u00famero se obtiene escribiendo los sucesivos sucesores de Collatz hasta llegar a 1. Por ejemplo, la \u00f3rbita de Collatz de 7 es 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.<\/p>\n\n
while<\/code>, la funci\u00f3n collatz<\/code> tal que collatz(n)<\/code> es la \u00f3rbita de Collatz de n<\/code>. Por ejemplo,<\/dt>\ncollatz(7) == [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]<\/code>\n<\/dd>\n<\/dl>\n\ndef collatz(n):\n s = [n]\n while (n != 1):\n if n % 2 == 0:\n n = n\/\/2\n else:\n n = 3*n+1\n s.append(n)\n return s\n<\/pre>\n
\n
collatz :: Integer -> [Integer]<\/code>\n<\/dd>\ncollatz 7 == [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]<\/code>\n<\/dd>\n<\/dl>\n\n-- 1\u00aa definici\u00f3n (con condicionales):\ncollatz :: Integer -> [Integer]\ncollatz n = reverse (aux [n])\n where aux (n:ns) = if n == 1 then n:ns\n else if even n \n then aux (div n 2:n:ns)\n else aux (3*n+1:n:ns)\n\n-- 2\u00aa definici\u00f3n (con guardas):\ncollatz2 :: Integer -> [Integer]\ncollatz2 n = reverse (aux [n])\n where aux (1:ns) = 1:ns\n aux (n:ns) | even n = aux (div n 2:n:ns)\n | otherwise = aux (3*n+1:n:ns)\n<\/pre>\n
\n
while1<\/code>, la<\/dt>\ncollatz :: Integer -> [Integer]<\/code>\n<\/dd>\n(collatz n)<\/code> es la \u00f3rbita de Collatz de n<\/code>. Por ejemplo,<\/dt>\ncollatz 7 == [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]<\/code>\n<\/dd>\n<\/dl>\n\ncollatz :: Int -> [Int]\ncollatz n = reverse (aux [n]) where\n aux = while1 (\\(n:ns) -> n \/= 1)\n (\\(n:ns) -> if even n \n then (n `div` 2):n:ns \n else (3*n+1):n:ns)\n<\/pre>\n
\n
mpf :: Eq a => (a -> a) -> a -> a<\/code>\n<\/dd>\n(mpf f x)<\/code> es el menor punto fijo de f<\/code> respecto de x<\/code>. Por ejemplo,<\/dt>\nmpf (\\x -> if x < 10 then x else (div x 10)) 325 == 3<\/code>\n<\/dd>\nmpf (\\x -> if even x then (div x 2) else x) 24 == 3<\/code><\/dd>\n<\/dl>\n\nmpf :: Eq a => (a -> a) -> a -> a\nmpf f x | f x == x = x\n | otherwise = mpf f (f x)\n<\/pre>\n
\n
while1<\/code>, la funci\u00f3n<\/dt>\nmpf :: Eq a => (a -> a) -> a -> a<\/code>\n<\/dd>\n(mpf f x)<\/code> es el menor punto fijo de f<\/code> respecto de x<\/code>. Por ejemplo,<\/dt>\nmpf (\\x -> if x < 10 then x else (div x 10)) 325 == 3<\/code>\n<\/dd>\nmpf (\\x -> if even x then (div x 2) else x) 24 == 3<\/code><\/dd>\n<\/dl>\n\nmpf :: Eq a => (a -> a) -> a -> a\nmpf f = while1 (\\x -> f x \/= x) (\\x -> f x)\n<\/pre>\n
El bucle while con dos par\u00e1metros<\/h2>\n
\n
while<\/code>, la funci\u00f3n sumaImpares<\/code> tal que sumaImpares(n)<\/code> es la suma de los n<\/code> primeros n\u00fameros impares. Por ejemplo,<\/dt>\nsumaImpares(3) == 9<\/code>\n<\/dd>\nsumaImpares(4) == 16<\/code><\/dd>\n<\/dl>\n\ndef sumaImpares(n): \n s = 0\n k = 0\n while k < n:\n s = s + 2*k + 1\n k = k + 1\n return s\n<\/pre>\n
\n
sumaImpares :: Int -> Int<\/code>\n<\/dd>\n<\/dl>\n\n-- 1\u00aa definici\u00f3n\nsumaImpares :: Int -> Int\nsumaImpares n = aux n 0 0 where\n aux n k s = if k < n then \n let s1 = s + 2*k + 1\n k1 = k + 1\n in aux n k1 s1 \n else s\n\n-- 2\u00aa definici\u00f3n (usando where en lugar de let)\nsumaImpares2 :: Int -> Int\nsumaImpares2 n = aux n 0 0 where\n aux n k s = if k < n \n then aux n k1 s1 \n else s\n where s1 = s + 2*k + 1\n k1 = k + 1\n\n-- 3\u00aa definici\u00f3n (sin let ni where)\nsumaImpares3 :: Int -> Int\nsumaImpares3 n = aux n 0 0 where\n aux n k s = if k < n \n then aux n (k + 1) (s + 2*k + 1)\n else s\n\n-- 4\u00aa definici\u00f3n (con guardas)\nsumaImpares4 :: Int -> Int\nsumaImpares4 n = aux n 0 0 where\n aux n k s | k < n = aux n (k + 1) (s + 2*k + 1)\n | otherwise = s\n<\/pre>\n
\n
while2 :: (a -> b -> Bool) -> (a -> b -> (a,b)) -> a -> b -> b<\/code>\n<\/dd>\n(while2 p f x y)<\/code> aplica f<\/code> a x<\/code> e y<\/code> mientras que se cumple la propiedad p<\/code> y devuelve y<\/code> cuando no se cumple. Por ejemplo,<\/dt>\n(while2 (\\x y -> x<3) (\\x y -> (x+1,x+y))) 0 0 == 3<\/code>\n<\/dd>\n(while2 (\\x y -> x<4) (\\x y -> (x+1,x+y))) 0 0 == 6<\/code><\/dd>\n<\/dl>\n(while2 p f x y)<\/code> es el siguiente<\/p>\n\n
(p x y)<\/code>, eval\u00faa (f x y)<\/code> que dar\u00e1 un par (x1,y1)<\/code><\/li>\n(p x1 y1)<\/code>, eval\u00faa (f x1 y1)<\/code> que dar\u00e1 un par (x2,y2)<\/code><\/li>\n(xn,yn)<\/code> tal que no se verifique (p xn yn)<\/code>, en cuyo caso devuelve yn<\/code>.<\/li>\n<\/ul>\n\nwhile2 :: (a -> b -> Bool) -> (a -> b -> (a,b)) -> a -> b -> b\nwhile2 p f x y \n | p x y = while2 p f x1 y1\n | otherwise = y \n where (x1,y1) = f x y\n<\/pre>\n
while2<\/code>, la funci\u00f3n sumaImpares<\/code>.<\/p>\n\nsumaImpares :: Int -> Int\nsumaImpares n = aux n 0 0 where\n aux n = while2\n (\\k s -> k < n)\n (\\k s -> (k+1,s+2*k+1))\n<\/pre>\n
mcd<\/code> tal que mcd(x,y)<\/code> es el m\u00e1ximo com\u00fan divisor de x<\/code> e y<\/code>, calculado mediante el algoritmo de Euclides.<\/p>\n\ndef mcd(x,y):\n while x != y:\n if x > y: \n x = x - y \n else: \n y = y - x\n return y\n<\/pre>\n
\n
mcd :: Int -> Int -> Int<\/code>\n<\/dd>\n<\/dl>\nmcd(x,y)<\/code> es el m\u00e1ximo com\u00fan divisor de x<\/code> e y<\/code>, calculado mediante el algoritmo de Euclides.<\/p>\n\nmcd :: Int -> Int -> Int\nmcd x y | x \/= y = if x > y \n then mcd (x-y) y\n else mcd x (y-x)\n | otherwise = y\n<\/pre>\n
while2<\/code>, la funci\u00f3n mcd<\/code>.<\/p>\n\nmcd2 :: Int -> Int -> Int\nmcd2 = while2 \n (\\ x y -> x \/= y) \n (\\ x y -> if x > y \n then (x-y,y) \n else (x,y-x))\n<\/pre>\n
\n
while<\/code>, la funci\u00f3n fact<\/code> tal que fact(n)<\/code> es el factorial de n<\/code>. Por ejemplo,<\/dt>\nfact(4) == 24<\/code>\n<\/dd>\n<\/dl>\n\ndef factorial(n):\n f = 1\n while n != 0:\n f = f*n\n n = n-1\n return f\n<\/pre>\n
\n
fact :: Integer -> Integer<\/code>\n<\/dd>\n(fact n)<\/code> es el factorial de `n. Por ejemplo,<\/dt>\nfact 4 == 24<\/code>\n<\/dd>\n<\/dl>\n\n-- 1\u00aa definici\u00f3n (con acumulador):\nfactorial :: Integer -> Integer\nfactorial n = aux n 1\n where aux 0 f = f\n aux n f = aux (n-1) (n*f)\n\n-- 2\u00aa definici\u00f3n (sin acumulador):\nfactorial2 :: Integer -> Integer\nfactorial2 0 = 1\nfactorial2 n = n * factorial2 (n-1)\n<\/pre>\n
while2<\/code>, la funci\u00f3n fact<\/code>.<\/p>\n\n-- 1\u00aa definici\u00f3n (con auxiliar):\nfactorial :: Integer -> Integer\nfactorial n = aux n 1\n where aux = while2 (\\n f -> n \/= 0)\n (\\n f -> (n-1,f*n))\n\n-- 2\u00aa definici\u00f3n (sin auxiliar):\nfactorial2 :: Integer -> Integer\nfactorial2 n = (while2 (\\n f -> n \/= 0)\n (\\n f -> (n-1,f*n))) n 1\n<\/pre>\n
El bucle while con tres par\u00e1metros<\/h2>\n
\n
fib<\/code> tal que fib(n)<\/code> es el n<\/code>-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de Fibonacci. Por ejemplo,<\/dt>\n[fib(n) for n in range(10)] == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]<\/code>\n<\/dd>\n<\/dl>\n\n# 1\u00aa definici\u00f3n\ndef fib(n):\n x = 0\n y = 1\n while (n != 0):\n x, y = (y,x+y)\n n = n-1\n return x\n\n# 2\u00aa definici\u00f3n\ndef fib2(n):\n if n == 0:\n return 0\n else: \n x = 0\n y = 1\n while (n > 1):\n x, y = (y,x+y)\n n = n-1\n return y\n<\/pre>\n
\n