PDF de programación - Tema 6: Funciones recursivas - Informática (2016–17)

Tema 6: Funciones recursivas - Informática (2016–17)gráfica de visualizaciones

Publicado el 6 de Agosto del 2017
511 visualizaciones desde el 6 de Agosto del 2017
232,9 KB
65 paginas
Creado hace 4a (12/09/2016)
Tema 6: Funciones recursivas

Informática (2016–17)

José A. Alonso Jiménez

Grupo de Lógica Computacional

Departamento de Ciencias de la Computación e I.A.

Universidad de Sevilla

IM Tema 6: Funciones recursivas

Tema 6: Funciones recursivas

1. Recursión numérica

2. Recusión sobre lista

3. Recursión sobre varios argumentos

4. Recursión múltiple

5. Recursión mutua

6. Heurísticas para las definiciones recursivas

2 / 24

IM Tema 6: Funciones recursivas

Recursión numérica

Recursión numérica: El factorial

La función factorial:

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n-1)

Cálculo:

factorial 3 = 3 * (factorial 2)

= 3 * (2 * (factorial 1))
= 3 * (2 * (1 * (factorial 0)))
= 3 * (2 * (1 * 1))
= 3 * (2 * 1)
= 3 * 2
= 6

3 / 24

IM Tema 6: Funciones recursivas

Recursión numérica

Recursión numérica: El factorial

La función factorial:

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n-1)

Cálculo:

factorial 3 = 3 * (factorial 2)

= 3 * (2 * (factorial 1))
= 3 * (2 * (1 * (factorial 0)))
= 3 * (2 * (1 * 1))
= 3 * (2 * 1)
= 3 * 2
= 6

3 / 24

IM Tema 6: Funciones recursivas

Recursión numérica

Recursión numérica: El factorial

La función factorial:

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n-1)

Cálculo:

factorial 3 = 3 * (factorial 2)

= 3 * (2 * (factorial 1))
= 3 * (2 * (1 * (factorial 0)))
= 3 * (2 * (1 * 1))
= 3 * (2 * 1)
= 3 * 2
= 6

3 / 24

IM Tema 6: Funciones recursivas

Recursión numérica

Recursión numérica: El producto

Definición recursiva del producto:

por :: Int -> Int -> Int
m `por` 0
m `por` n

= 0
= m + (m `por` (n-1))

Cálculo:

3 `por` 2 = 3 + (3 `por` 1)

= 3 + (3 + (3 `por` 0))
= 3 + (3 + 0)
= 3 + 3
= 6

4 / 24

IM Tema 6: Funciones recursivas

Recursión numérica

Recursión numérica: El producto

Definición recursiva del producto:

por :: Int -> Int -> Int
m `por` 0
m `por` n

= 0
= m + (m `por` (n-1))

Cálculo:

3 `por` 2 = 3 + (3 `por` 1)

= 3 + (3 + (3 `por` 0))
= 3 + (3 + 0)
= 3 + 3
= 6

4 / 24

IM Tema 6: Funciones recursivas

Recursión numérica

Recursión numérica: El producto

Definición recursiva del producto:

por :: Int -> Int -> Int
m `por` 0
m `por` n

= 0
= m + (m `por` (n-1))

Cálculo:

3 `por` 2 = 3 + (3 `por` 1)

= 3 + (3 + (3 `por` 0))
= 3 + (3 + 0)
= 3 + 3
= 6

4 / 24

IM Tema 6: Funciones recursivas

Recusión sobre lista

Recursión sobre listas: La función product

Producto de una lista de números:

Prelude

product :: Num a => [a] -> a
product []
product (n:ns) = n * product ns

= 1

Cálculo:

product [7,5,2] = 7 * (product [5,2])

= 7 * (5 * (product [2]))
= 7 * (5 * (2 * (product [])))
= 7 * (5 * (2 * 1))
= 7 * (5 * 2)
= 7 * 10
= 70

5 / 24

IM Tema 6: Funciones recursivas

Recusión sobre lista

Recursión sobre listas: La función product

Producto de una lista de números:

Prelude

product :: Num a => [a] -> a
product []
product (n:ns) = n * product ns

= 1

Cálculo:

product [7,5,2] = 7 * (product [5,2])

= 7 * (5 * (product [2]))
= 7 * (5 * (2 * (product [])))
= 7 * (5 * (2 * 1))
= 7 * (5 * 2)
= 7 * 10
= 70

5 / 24

IM Tema 6: Funciones recursivas

Recusión sobre lista

Recursión sobre listas: La función product

Producto de una lista de números:

Prelude

product :: Num a => [a] -> a
product []
product (n:ns) = n * product ns

= 1

Cálculo:

product [7,5,2] = 7 * (product [5,2])

= 7 * (5 * (product [2]))
= 7 * (5 * (2 * (product [])))
= 7 * (5 * (2 * 1))
= 7 * (5 * 2)
= 7 * 10
= 70

5 / 24

IM Tema 6: Funciones recursivas

Recusión sobre lista

Recursión sobre listas: La función length

Longitud de una lista:

Prelude

length :: [a] -> Int
length []
length (_:xs) = 1 + length xs

= 0

Cálculo:

length [2,3,5] = 1 + (length [3,5])

= 1 + (1 + (length [5]))
= 1 + (1 + (1 + (length [])))
= 1 + (1 + (1 + 0))
= 1 + (1 + 1)
= 1 + 2
= 3

6 / 24

IM Tema 6: Funciones recursivas

Recusión sobre lista

Recursión sobre listas: La función length

Longitud de una lista:

Prelude

length :: [a] -> Int
length []
length (_:xs) = 1 + length xs

= 0

Cálculo:

length [2,3,5] = 1 + (length [3,5])

= 1 + (1 + (length [5]))
= 1 + (1 + (1 + (length [])))
= 1 + (1 + (1 + 0))
= 1 + (1 + 1)
= 1 + 2
= 3

6 / 24

IM Tema 6: Funciones recursivas

Recusión sobre lista

Recursión sobre listas: La función length

Longitud de una lista:

Prelude

length :: [a] -> Int
length []
length (_:xs) = 1 + length xs

= 0

Cálculo:

length [2,3,5] = 1 + (length [3,5])

= 1 + (1 + (length [5]))
= 1 + (1 + (1 + (length [])))
= 1 + (1 + (1 + 0))
= 1 + (1 + 1)
= 1 + 2
= 3

6 / 24

IM Tema 6: Funciones recursivas

Recusión sobre lista

Recursión sobre listas: La función reverse

Inversa de una lista:

Prelude

reverse :: [a] -> [a]
reverse []
reverse (x:xs) = reverse xs ++ [x]

= []

Cálculo:

reverse [2,5,3] = (reverse [5,3]) ++ [2]

= ((reverse [3]) ++ [5]) ++ [2]
= (((reverse []) ++ [3]) ++ [5]) ++ [2]
= (([] ++ [3]) ++ [5]) ++ [2]
= ([3] ++ [5]) ++ [2]
= [3,5] ++ [2]
= [3,5,2]

7 / 24

IM Tema 6: Funciones recursivas

Recusión sobre lista

Recursión sobre listas: La función reverse

Inversa de una lista:

Prelude

reverse :: [a] -> [a]
reverse []
reverse (x:xs) = reverse xs ++ [x]

= []

Cálculo:

reverse [2,5,3] = (reverse [5,3]) ++ [2]

= ((reverse [3]) ++ [5]) ++ [2]
= (((reverse []) ++ [3]) ++ [5]) ++ [2]
= (([] ++ [3]) ++ [5]) ++ [2]
= ([3] ++ [5]) ++ [2]
= [3,5] ++ [2]
= [3,5,2]

7 / 24

IM Tema 6: Funciones recursivas

Recusión sobre lista

Recursión sobre listas: La función reverse

Inversa de una lista:

Prelude

reverse :: [a] -> [a]
reverse []
reverse (x:xs) = reverse xs ++ [x]

= []

Cálculo:

reverse [2,5,3] = (reverse [5,3]) ++ [2]

= ((reverse [3]) ++ [5]) ++ [2]
= (((reverse []) ++ [3]) ++ [5]) ++ [2]
= (([] ++ [3]) ++ [5]) ++ [2]
= ([3] ++ [5]) ++ [2]
= [3,5] ++ [2]
= [3,5,2]

7 / 24

IM Tema 6: Funciones recursivas

Recusión sobre lista

Recursión sobre listas: ++

Concatenación de listas:

Prelude

(++) :: [a] -> [a] -> [a]
[]
(x:xs) ++ ys = x : (xs ++ ys)

++ ys = ys

Cálculo:

[1,3,5] ++ [2,4] = 1:([3,5] ++ [2,4])

= 1:(3:([5] ++ [2,4]))
= 1:(3:(5:([] ++ [2,4])))
= 1:(3:(5:[2,4]))
= 1:(3:[5,2,4])
= 1:[3,5,2,4]
= [1,3,5,2,4]

8 / 24

IM Tema 6: Funciones recursivas

Recusión sobre lista

Recursión sobre listas: ++

Concatenación de listas:

Prelude

(++) :: [a] -> [a] -> [a]
[]
(x:xs) ++ ys = x : (xs ++ ys)

++ ys = ys

Cálculo:

[1,3,5] ++ [2,4] = 1:([3,5] ++ [2,4])

= 1:(3:([5] ++ [2,4]))
= 1:(3:(5:([] ++ [2,4])))
= 1:(3:(5:[2,4]))
= 1:(3:[5,2,4])
= 1:[3,5,2,4]
= [1,3,5,2,4]

8 / 24

IM Tema 6: Funciones recursivas

Recusión sobre lista

Recursión sobre listas: ++

Concatenación de listas:

Prelude

(++) :: [a] -> [a] -> [a]
[]
(x:xs) ++ ys = x : (xs ++ ys)

++ ys = ys

Cálculo:

[1,3,5] ++ [2,4] = 1:([3,5] ++ [2,4])

= 1:(3:([5] ++ [2,4]))
= 1:(3:(5:([] ++ [2,4])))
= 1:(3:(5:[2,4]))
= 1:(3:[5,2,4])
= 1:[3,5,2,4]
= [1,3,5,2,4]

8 / 24

IM Tema 6: Funciones recursivas

Recusión sobre lista

Recursión sobre listas: Inserción ordenada

(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]
= [e]
inserta e []
inserta e (x:xs) | e <= x
= e : (x:xs)
= x : inserta e xs

| otherwise

Cálculo:

inserta 4 [1,3,5,7] = 1:(inserta 4 [3,5,7])

= 1:(3:(inserta 4 [5,7]))
= 1:(3:(4:(5:[7])))
= 1:(3:(4:[5,7]))
= [1,3,4,5,7]

9 / 24

IM Tema 6: Funciones recursivas

Recusión sobre lista

Recursión sobre listas: Inserción ordenada

(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]
= [e]
inserta e []
inserta e (x:xs) | e <= x
= e : (x:xs)
= x : inserta e xs

| otherwise

Cálculo:

inserta 4 [1,3,5,7] = 1:(inserta 4 [3,5,7])

= 1:(3:(inserta 4 [5,7]))
= 1:(3:(4:(5:[7])))
= 1:(3:(4:[5,7]))
= [1,3,4,5,7]

9 / 24

IM Tema 6: Funciones recursivas

Recusión sobre lista

Recursión sobre listas: Inserción ordenada

(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]
= [e]
inserta e []
inserta e (x:xs) | e <= x
= e : (x:xs)
= x : inserta e xs

| otherwise

Cálculo:

inserta 4 [1,3,5,7] = 1:(inserta 4 [3,5,7])

= 1:(3:(inserta 4 [5,7]))
= 1:(3:(4:(5:[7])))
= 1:(3:(4:[5,7]))
= [1,3,4,5,7]

9 / 24

IM Tema 6: Funciones recursivas

Recusión sobre lista

Recursión sobre listas: Ordenación por inserción

(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)

Cálculo:

ordena_por_insercion [7,9,6] =

= inserta 7 (inserta 9 (inserta 6 []))
= inserta 7 (inserta 9 [6])
= inserta 7 [6,9]
= [6,7,9]

10 / 24

IM Tema 6: Funciones recursivas

Recusión sobre lista

Recursión sobre listas: Ordenación por inserción

(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)

Cálculo:

ordena_por_insercion [7,9,6] =

= inserta 7 (inserta 9 (inserta 6 []))
= inserta 7 (inserta 9 [6])
= i
  • Links de descarga
http://lwp-l.com/pdf6123

Comentarios de: Tema 6: Funciones recursivas - Informática (2016–17) (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad