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

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