Menu Close

Iteración, recursión y punto fijo

En esta relación de ejercicios se muestra cómo se pueden transformar programas iterativos (con bucles while o for) en programas en recursivos. Para cada uno de los bucles, se elige una función y se pide definirla usando el bucle (en Python), buscar una definición recursiva que sea semejante a la anterior, definir el patrón que abstrae el bucle, definirla con el patrón y aplicar el patrón a otras funciones. Finalmente, se estudia cómo definir algunas de las anteriores funciones usando el menor punto fijo.

La relación está elaborado como complemento del tema Funciones de orden superior del curso de Informática de primero del Grado en Matemáticas.

El bucle while con un parámetro

Nota [Parte impar]. Todo número entero n se puede escribir como m*2^k, con m impar. Se dice que m es la parte impar de n. Por ejemplo, la parte impar de 40 es 5 porque 40 = 5*2^3.

Ejercicio 1 [Parte impar con while en Python]. Definir en Python, usando un blucle while, la función parteImpar tal que parteImpar(n) es la parte impar de n.

Solución:

def parteImpar(n): 
    while n % 2 == 0:
        n = n/2
    return n
Ejercicio 2 [Parte impar por recursión]. Definir, por recursión, la función
parteImpar :: Int -> Int
tal que (parteImpar n) es la parte impar de n. Por ejemplo,
parteImpar 40 == 5

Solución:

parteImpar :: Int -> Int
parteImpar n | even n    = parteImpar (n `div` 2)
             | otherwise = n
Ejercicio 3 [El bucle while1]. Definir la función
while1 :: (a -> Bool) -> (a -> a) -> a -> a
tal que (while1 p f x) es el resultado de aplicar la función f a x mientras cumple la propiedad p. Por ejemplo,
while1 (<1000) (*2) 1 == 1024

Solución:

-- 1ª definición (por recursión):
while1 :: (a -> Bool) -> (a -> a) -> a -> a
while1 p f x | p x       = while1 p f (f x)
             | otherwise = x
 
-- 2ª definición (con until):
while1b :: (a -> Bool) -> (a -> a) -> a -> a
while1b p f x = until (not . p) f x
 
-- 3ª definición (con until y composición):
while1c :: (a -> Bool) -> (a -> a) -> a -> a
while1c = until . (not.)

Ejercicio 4 [Parte impar con el bucle while1]. Redefinir, usando while1, la función parteImpar.

Solución:

parteImpar2 :: Int -> Int
parteImpar2 = while1 even (`div` 2)

Nota [La órbita de Collatz]. El sucesor de Collatz de un número n es n/2, si n es par y 3n+1 , en caso contrario. La órbita de un número se obtiene escribiendo los sucesivos sucesores de Collatz hasta llegar a 1. Por ejemplo, la órbita de Collatz de 7 es 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Ejercicio 5 [La órbita de Collatz con while en Python]. Definir en Python, usando while, la función collatz tal que collatz(n) es la órbita de Collatz de n. Por ejemplo,
collatz(7) == [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]

Solución:

def collatz(n):
    s = [n]
    while (n != 1):
        if n % 2 == 0:
            n = n//2
        else:
            n = 3*n+1
        s.append(n)
    return s
Ejercicio 6 [La órbita de Collatz por recursión]. Definir, mediante recursión, la función
collatz :: Integer -> [Integer]
tal que (collatz n) es la órbita de Collatz de n. Por ejemplo,
collatz 7 == [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]

Solución:

-- 1ª definición (con condicionales):
collatz :: Integer -> [Integer]
collatz n = reverse (aux [n])
    where aux (n:ns) = if n == 1 then n:ns
                       else if even n 
                            then aux (div n 2:n:ns)
                            else aux (3*n+1:n:ns)
 
-- 2ª definición (con guardas):
collatz2 :: Integer -> [Integer]
collatz2 n = reverse (aux [n])
    where aux (1:ns) = 1:ns
          aux (n:ns) | even n    = aux (div n 2:n:ns)
                     | otherwise = aux (3*n+1:n:ns)
Ejercicio 7 [La órbita de Collatz con while1]. Definir, usando while1, la
función
collatz :: Integer -> [Integer]
tal que (collatz n) es la órbita de Collatz de n. Por ejemplo,
collatz 7 == [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]

Solución:

collatz :: Int -> [Int]
collatz n = reverse (aux [n]) where
    aux = while1 (\(n:ns) -> n /= 1)
                 (\(n:ns) -> if even n 
                             then (n `div` 2):n:ns 
                             else (3*n+1):n:ns)
Ejercicio 8 [El menor punto fijo por recursión]. Definir, por recursión, la función
mpf :: Eq a => (a -> a) -> a -> a
tal que (mpf f x) es el menor punto fijo de f respecto de x. Por ejemplo,
mpf (\x -> if x < 10 then x else (div x 10)) 325 == 3
mpf (\x -> if even x then (div x 2) else x) 24 == 3

Solución:

mpf :: Eq a => (a -> a) -> a -> a
mpf f x | f x == x  = x
        | otherwise = mpf f (f x)
Ejercicio 9 [El menor punto fijo con while1]. Definir, con while1, la función
mpf :: Eq a => (a -> a) -> a -> a
tal que (mpf f x) es el menor punto fijo de f respecto de x. Por ejemplo,
mpf (\x -> if x < 10 then x else (div x 10)) 325 == 3
mpf (\x -> if even x then (div x 2) else x) 24 == 3

Solución:

mpf :: Eq a => (a -> a) -> a -> a
mpf f = while1 (\x -> f x /= x) (\x -> f x)

El bucle while con dos parámetros

Ejercicio 10 [Suma impares con bucle while en Python]. Definir en Python, usando un bucle while, la función sumaImpares tal que sumaImpares(n) es la suma de los n primeros números impares. Por ejemplo,
sumaImpares(3) == 9
sumaImpares(4) == 16

Solución:

def sumaImpares(n): 
    s = 0
    k = 0
    while k < n:
        s = s + 2*k + 1
        k = k + 1
    return s
Ejercicio 11 [Suma impares por recursión]. Definir en Haskell la función
sumaImpares :: Int -> Int

que traduzca la definición anterior.

Solución:

-- 1ª definición
sumaImpares :: Int -> Int
sumaImpares n = aux n 0 0 where
    aux n k s = if k < n then 
                    let s1 = s + 2*k + 1
                        k1 = k + 1
                    in aux n k1 s1 
                else s
 
-- 2ª definición (usando where en lugar de let)
sumaImpares2 :: Int -> Int
sumaImpares2 n = aux n 0 0 where
    aux n k s = if k < n 
                then aux n k1 s1  
                else s
                where s1 = s + 2*k + 1
                      k1 = k + 1
 
-- 3ª definición (sin let ni where)
sumaImpares3 :: Int -> Int
sumaImpares3 n = aux n 0 0 where
    aux n k s = if k < n 
                then aux n (k + 1) (s + 2*k + 1)
                else s
 
-- 4ª definición (con guardas)
sumaImpares4 :: Int -> Int
sumaImpares4 n = aux n 0 0 where
    aux n k s | k < n     = aux n (k + 1) (s + 2*k + 1)
              | otherwise = s
Ejercicio 12 [El bucle while2] Definir la función
while2 :: (a -> b -> Bool) -> (a -> b -> (a,b)) -> a -> b -> b
tal que (while2 p f x y) aplica f a x e y mientras que se cumple la propiedad p y devuelve y cuando no se cumple. Por ejemplo,
(while2 (\x y -> x<3) (\x y -> (x+1,x+y))) 0 0 == 3
(while2 (\x y -> x<4) (\x y -> (x+1,x+y))) 0 0 == 6

El procedimiento de evaluación de (while2 p f x y) es el siguiente

  • si se verifica (p x y), evalúa (f x y) que dará un par (x1,y1)
  • si se verifica (p x1 y1), evalúa (f x1 y1) que dará un par (x2,y2)
  • y así hasta que llegue a un par (xn,yn) tal que no se verifique (p xn yn), en cuyo caso devuelve yn.

Solución:

while2 :: (a -> b -> Bool) -> (a -> b -> (a,b)) -> a -> b -> b
while2 p f x y 
    | p x y     = while2 p f x1 y1
    | otherwise = y 
    where (x1,y1) = f x y

Ejercicio 13 [Suma impares con while2]. Redefinir, usando while2, la función sumaImpares.

Solución:

sumaImpares :: Int -> Int
sumaImpares n = aux n 0 0 where
    aux n = while2
             (\k s -> k < n)
             (\k s -> (k+1,s+2*k+1))

Ejercicio 14 [El algoritmo de Euclides con while en Python]. Definir en Python la función mcd tal que mcd(x,y) es el máximo común divisor de x e y, calculado mediante el algoritmo de Euclides.

Solución:

def mcd(x,y):
    while x != y:
        if x > y: 
            x = x - y 
        else: 
            y = y - x
    return y
Ejercicio 15 [El algoritmo de Euclides por recursión]. Definir la función
mcd :: Int -> Int -> Int

tal que mcd(x,y) es el máximo común divisor de x e y, calculado mediante el algoritmo de Euclides.

Solución:

mcd :: Int -> Int -> Int
mcd x y | x /= y    = if x > y 
                      then mcd (x-y) y
                      else mcd x (y-x)
        | otherwise = y

Ejercicio 16 [El algoritmo de Euclides con while2]. Redefinir, usando while2, la función mcd.

Solución:

mcd2 :: Int -> Int -> Int
mcd2 = while2 
       (\ x y -> x /= y) 
       (\ x y -> if x > y 
                 then (x-y,y) 
                 else (x,y-x))
Ejercicio 17 [El factorial con while en Python]. Definir en Python, usando while, la función fact tal que fact(n) es el factorial de n. Por ejemplo,
fact(4) == 24

Solución:

def factorial(n):
    f = 1
    while n != 0:
        f = f*n
        n = n-1
    return f
Ejercicio 18 [El factorial por recursión]. Definir, por recursión, la función
fact :: Integer -> Integer
tal que (fact n) es el factorial de `n. Por ejemplo,
fact 4 == 24

Solución:

-- 1ª definición (con acumulador):
factorial :: Integer -> Integer
factorial n = aux n 1
    where aux 0 f = f
          aux n f = aux (n-1) (n*f)
 
-- 2ª definición (sin acumulador):
factorial2 :: Integer -> Integer
factorial2 0 = 1
factorial2 n = n * factorial2 (n-1)

Ejercicio 19 [El factorial con while2]. Redefinir, con while2, la función fact.

Solución:

-- 1ª definición (con auxiliar):
factorial :: Integer -> Integer
factorial n = aux n 1
    where aux = while2 (\n f -> n /= 0)
                       (\n f -> (n-1,f*n))
 
-- 2ª definición (sin auxiliar):
factorial2 :: Integer -> Integer
factorial2 n = (while2 (\n f -> n /= 0)
                       (\n f -> (n-1,f*n))) n 1

El bucle while con tres parámetros

Ejercicio 20 [Fibonacci con while en Python]. Definir la función fib tal que fib(n) es el n-ésimo término de la sucesión de Fibonacci. Por ejemplo,
[fib(n) for n in range(10)] == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Solución:

# 1ª definición
def fib(n):
    x = 0
    y = 1
    while (n != 0):
        x, y = (y,x+y)
        n = n-1
    return x
 
# 2ª definición
def fib2(n):
    if n == 0:
        return 0
    else: 
        x = 0
        y = 1
        while (n > 1):
            x, y = (y,x+y)
            n = n-1
        return y
Ejercicio 21 [Fibonacci por recursión]. Definir, por recursión, la función
fib :: Int -> Int
tal que (fib n) es el n-ésimo término de la sucesión de Fibonacci. Por ejemplo,
[fib n | n <- [0..9]] == [0,1,1,2,3,5,8,13,21,34]

Solución:

-- 1ª definición (semejante a la iterativa con while)
fib :: Int -> Int
fib 0 = 0
fib n = aux (n-1) 0 1 where
    aux 0 x y = y
    aux n x y = aux (n-1) y (x+y)
 
-- 2ª definición:
fib2 :: Int -> Int
fib2 n = aux n 0 1 where
     aux 0 x y = x
     aux n x y = aux (n-1) y (x+y)
Ejercicio 22 [El bucle while3]. Definir la función
while3 :: (a -> b -> c -> Bool) -> (a -> b -> c -> (a,b,c)) -> a -> b -> c -> c`
tal que (while3 p f x y z) es una generalización de while2 con tres parámetros. Por ejemplo,
while3 (\n x y -> n > 0)(\n x y -> (n-1,y,x+y)) 5 0 1 == 8
while3 (\n x y -> n > 0)(\n x y -> (n-1,y,x+y)) 6 0 1 == 13
while3 (\n x y -> n > 0)(\n x y -> (n-1,y,x+y)) 7 0 1 == 21

Solución:

while3 :: (a -> b -> c -> Bool)
       -> (a -> b -> c -> (a,b,c))
       -> a -> b -> c -> c
while3 p f x y z 
    | p x y z   = while3 p f x1 y1 z1
    | otherwise = z 
    where (x1,y1,z1) = f x y z

Ejercicio 23 [Fibonacci con while3]. Redefinir, con while3, la función fib.

Solución:

fib :: Int -> Int
fib 0 = 0
fib n = aux (n-1) 0 1 where
    aux = while3 (\n x y -> n /= 0)
                 (\n x y -> (n-1,y,x+y))

El bucle for con un parámetro

Ejercicio 24 [El factorial con for en Python]. Definir en Python, usando for, la función fact tal que fact(n) es el factorial de n. Por ejemplo,
fact(4) == 24

Solución:

def factorial(n):
    f = 1
    for k in range(1,n+1):
        f = k*f
    return f
Ejercicio 25 [El bucle for]. Definir la función
for :: [a] -> (a -> b -> b) -> b -> b
tal que (for xs f y) es el resultado de iterar f sobre los elementos de xs a partir de y; es decir, si xs es [x(1),...,x(n)] entonces (for xs f y) es (f x(n) (f x(n-2) (... (f x(2) (f x(1) y))))). Por ejemplo,
(for [1..4] (\x s -> x+s)) 0 == 10
(for [1..4] (\x s -> x*s)) 1 == 24

Solución:

-- 1ª definición (por recursión):
for :: [a] -> (a -> b -> b) -> b -> b
for []     f y = y
for (x:xs) f y = for xs f (f x y)
 
-- 2ª definición (por plegado):
forP :: [a] -> (a -> b -> b) -> b -> b
forP xs f y = foldr f y xs

Ejercicio 26 [El factorial con for]. Reefinir, usando for, la función fact.

Solución:

fact :: Integer -> Integer
fact n = for [1..n] (\ k f -> k*f) 1

El bucle for con dos parámetros

Ejercicio 27 [Fibonacci con for en Python]. Definir en Python, usando for, la función fib tal que fib(n) es el n-ésimo término de la sucesión de Fibonacci. Por ejemplo,
[fib(n) for n in range(10)] == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Solución:

# 1ª definición
def fib(n):
    x = 0
    y = 1
    for k in range(n):
        x, y = (y,x+y)
    return x
 
# 2ª definición
def fib2(n):
    if n == 0:
        return 0
    else:
        x = 0
        y = 1
        for k in range(1,n):
            x, y = (y,x+y)
        return y
Ejercicio 28 [El bucle for2]. Definir el bucle for con 2 parámetros. Por ejemplo.
for2 [1..9] (\x y z -> (x+y,y:z)) 0 [] == [36,28,21,15,10,6,3,1,0]
for2 [1..7] (\x y z -> (x*y,y:z)) 1 [] == [720,120,24,6,2,1,1]

Solución:

for2 :: [a] -> (a -> b -> c -> (b,c)) -> b -> c -> c
for2 []     f _ z = z
for2 (x:xs) f y z = for2 xs f y1 z1
    where (y1,z1) = f x y z

Ejercicio 29 [Fibonacci con for2]. Redefinir, con for2, la función fib.

Solución:

fib :: Int -> Int
fib 0 = 0
fib n = aux (n-1) 0 1 where
    aux n = for2 [1..n] (\k x y -> (y,x+y))

Recursión y puntos fijos

Nota. En esta sección se proponen ejercicios para eliminar la recursión mediante puntos fijos; en concreto, usando la función fix tal que (fix f) es el menor punto fijo de f. La función fix está definida en la librería Data.Function como

fix :: (a -> a) -> a
fix f = f (fix f)
Ejercicio 30 [Factorial mediante fix]. Definir, usando fix, la función
fact :: Integer -> Integer
tal que (fact n) es el factorial de n. Por ejemplo,
[fact n | n <- [0..6]] == [1,1,2,6,24,120,720]

Solución:

import Data.Function (fix)
 
-- 1ª definición (con auxiliar)
fact :: Integer -> Integer
fact = fix aux
 
aux :: (Integer -> Integer) -> Integer -> Integer
aux f n = if n == 0 then 1 else n * f (n-1)
 
-- Cálculo de (fact 3)
--    fact 3 =
--    = (fix aux) 3
--    = aux (fix aux) 3
--    = 3 * ((fix aux) 2)
--    = 3 * (aux (fix aux) 2)
--    = 3 * (2 * ((fix aux) 1))
--    = 3 * (2 * ((fix aux) 1))
--    = 3 * (2 * (aux (fix aux) 1))
--    = 3 * (2 * (1 * ((fix aux) 0)))
--    = 3 * (2 * (1 * 1))
--    = 6
 
-- 2ª definición (sin auxiliar)
fact2 :: Integer -> Integer
fact2 = fix (\f n -> if n == 0 then 1 else n * f (n-1))
 
-- Nota. Puesto que fact es punto fijo de aux, se tiene
--    fact = aux fact
--         = (\f n -> if n == 0 then 1 else n * f (n-1)) fact
--         = \n -> if n == 0 then 1 else n * fact (n-1)
Ejercicio 31 [Fibonacci mediante fix]. Definir, usando fix, la función
fib :: Int -> Int
tal que (fib n) es el n-ésimo término de la sucesión de Fibonacci. Por ejemplo,
[fib n | n <- [0..9]] == [0,1,1,2,3,5,8,13,21,34]

Solución:

import Data.Function (fix)
 
-- 1ª definición (con auxiliares)
fib :: Int -> Int
fib = fibAux 0 1 where
    fibAux      = fix aux 
    aux f x y n = if n == 0 then x else f y (x+y) (n-1)
 
-- Cálculo de (fib 6)
--    fib 6
--    = fibAux 0 1 6
--    = (fix aux) 0 1 6
--    = aux (fix aux) 0 1 6
--    = (fix aux) 1 1 5
--    = aux (fix aux) 1 1 5
--    = (fix aux) 1 2 4
--    = aux (fix aux) 1 2 4
--    = (fix aux) 2 3 3
--    = aux (fix aux) 2 3 3
--    = (fix aux) 3 5 2
--    = aux (fix aux) 3 5 2
--    = (fix aux) 5 8 1
--    = aux (fix aux) 8 13 0
--    = 8
 
-- 2ª definición (sin auxiliares):
fib2 :: Int -> Int
fib2 = (fix (\f x y n -> if n == 0 then x else f y (x+y) (n-1))) 0 1
 
-- Nota. Puesto que fibAux es punto fijo de aux, se tiene
--    fibAux = aux fibAux
--           = (\f x y n -> if n == 0 then x else f y (x+y) (n-1)) fibAux 
--           = \x y n -> if n == 0 then x else fibAux y (x+y) (n-1)
Ejercicio 32 [La órbita de Collatz mediante fix]. Definir, usando fix, la función
collatz :: Integer -> [Integer]
tal que (collatz n) es la órbita de Collatz de n. Por ejemplo,
collatz 7 == [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]

Solución:

import Data.Function (fix)
 
-- 1ª definición (con auxiliares):
collatz :: Integer -> [Integer]
collatz n = reverse (collatzAux [n]) where
    collatzAux   = fix aux
    aux f (n:ns) = if n == 1 
                   then n:ns
                   else if even n 
                        then f (div n 2:n:ns)
                        else f (3*n+1:n:ns)
 
-- 2ª definición (sin auxiliares):
collatz2 :: Integer -> [Integer]
collatz2 n = 
   reverse ((fix (\f (n:ns) -> if n == 1 
                               then n:ns
                               else if even n 
                                    then f (div n 2:n:ns)
                                    else f (3*n+1:n:ns)))
            [n])
 
-- Nota: Puesto que collatzAux es un punto fijo de aux, se tiene
--    collatzAux = aux collatzAux
--               = (\f (n:ns) -> if n == 1 
--                               then n:ns
--                               else if even n 
--                                    then f (div n 2:n:ns)
--                                    else f (3*n+1:n:ns)) collatzAux
--               = \(n:ns) -> if n == 1 
--                            then n:ns
--                            else if even n 
--                                 then collatzAux (div n 2:n:ns)
--                                 else collatzAux (3*n+1:n:ns)
Ejercicio 33 [Suma impares mediante fix]. Definir, usando fix, la función
sumaImpares :: Int -> Int
tal que (sumaImpares n) es la suma de los primeros n números impares. Por ejemplo,
sumaImpares 3 == 9
sumaImpares 4 == 16

Solución:

import Data.Function (fix)
 
sumaImpares :: Int -> Int
sumaImpares n = sumaImparesAux n 0 0 where
    sumaImparesAux = fix aux
    aux f n k s | k < n     = f n (k + 1) (s + 2*k + 1)
                | otherwise = s

Referencias

Haskell