definicao_recursiva

Prévia do material em texto

Programação Funcional
Aula 5 - Definição recursiva
Wladimir Araújo Tavares 1
1Universidade Federal do Ceará - Campus de Quixadá
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 1 / 13
Definição recursiva
Uma definição de uma função é dita recursiva quando usamos a própria
função na sua definição. Por exemplo,
Sequência de Fibonacci:
F(0) = 1
F(1) = 1
F(n) = F(n-1) + F(n-2), ∀n ≥ 2
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 2 / 13
Definição recursiva
Sequência de Fibonacci:
F(0) = 1
F(1) = 1
F(n) = F(n-1) + F(n-2), ∀n ≥ 2
F(4) = F(3) + F(2)
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 3 / 13
Definição recursiva
Sequência de Fibonacci:
F(0) = 1
F(1) = 1
F(n) = F(n-1) + F(n-2), ∀n ≥ 2
F(4) = F(3) + F(2)
= F(2) + F(1) + F(2)
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 3 / 13
Definição recursiva
Sequência de Fibonacci:
F(0) = 1
F(1) = 1
F(n) = F(n-1) + F(n-2), ∀n ≥ 2
F(4) = F(3) + F(2)
= F(2) + F(1) + F(2)
= F(2) + F(1) + F(2)
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 3 / 13
Definição recursiva
Sequência de Fibonacci:
F(0) = 1
F(1) = 1
F(n) = F(n-1) + F(n-2), ∀n ≥ 2
F(4) = F(3) + F(2)
= F(2) + F(1) + F(2)
= F(2) + F(1) + F(2)
= F(1) + F(0) + F(1) + F(2)
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 3 / 13
Definição recursiva
Sequência de Fibonacci:
F(0) = 1
F(1) = 1
F(n) = F(n-1) + F(n-2), ∀n ≥ 2
F(4) = F(3) + F(2)
= F(2) + F(1) + F(2)
= F(2) + F(1) + F(2)
= F(1) + F(0) + F(1) + F(2)
= 1 + 1 + F(1) + F(2)
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 3 / 13
Definição recursiva
Sequência de Fibonacci:
F(0) = 1
F(1) = 1
F(n) = F(n-1) + F(n-2), ∀n ≥ 2
F(4) = F(3) + F(2)
= F(2) + F(1) + F(2)
= F(2) + F(1) + F(2)
= F(1) + F(0) + F(1) + F(2)
= 1 + 1 + F(1) + F(2)
= 2 + F(1) + F(2)
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 3 / 13
Definição recursiva
Sequência de Fibonacci:
F(0) = 1
F(1) = 1
F(n) = F(n-1) + F(n-2), ∀n ≥ 2
F(4) = F(3) + F(2)
= F(2) + F(1) + F(2)
= F(2) + F(1) + F(2)
= F(1) + F(0) + F(1) + F(2)
= 1 + 1 + F(1) + F(2)
= 2 + F(1) + F(2)
= 2 + 1 + F(2)
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 3 / 13
Definição recursiva
Sequência de Fibonacci:
F(0) = 1
F(1) = 1
F(n) = F(n-1) + F(n-2), ∀n ≥ 2
F(4) = F(3) + F(2)
= F(2) + F(1) + F(2)
= F(2) + F(1) + F(2)
= F(1) + F(0) + F(1) + F(2)
= 1 + 1 + F(1) + F(2)
= 2 + F(1) + F(2)
= 2 + 1 + F(2)
= 3 + F(1) + F(0)
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 3 / 13
Definição recursiva
Sequência de Fibonacci:
F(0) = 1
F(1) = 1
F(n) = F(n-1) + F(n-2), ∀n ≥ 2
F(4) = F(3) + F(2)
= F(2) + F(1) + F(2)
= F(2) + F(1) + F(2)
= F(1) + F(0) + F(1) + F(2)
= 1 + 1 + F(1) + F(2)
= 2 + F(1) + F(2)
= 2 + 1 + F(2)
= 3 + F(1) + F(0)
= 3 + 2
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 3 / 13
Definição recursiva
Sequência de Fibonacci:
F(0) = 1
F(1) = 1
F(n) = F(n-1) + F(n-2), ∀n ≥ 2
F(4) = F(3) + F(2)
= F(2) + F(1) + F(2)
= F(2) + F(1) + F(2)
= F(1) + F(0) + F(1) + F(2)
= 1 + 1 + F(1) + F(2)
= 2 + F(1) + F(2)
= 2 + 1 + F(2)
= 3 + F(1) + F(0)
= 3 + 2
= 5
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 3 / 13
Função length
Defina a função length :: [a] -> Int tal que (length xs) devolve o
tamanho da lista xs. Por exemplo,
length [1,2,3,4,6] == 5
A função length transforma
(Caso mais simples) A lista vazia em 0
length [] = 0
(Caso recursivo) A lista não vazia (x:xs) em 1 mais o length da lista
xs.
length (x:xs) = 1 + length xs
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 4 / 13
Função length
Defina a função length :: [a] -> Int tal que (length xs) devolve o
tamanho da lista xs. Por exemplo,
length [1,2,3,4,6] == 5
A função length transforma
(Caso mais simples) A lista vazia em 0
length [] = 0
(Caso recursivo) A lista não vazia (x:xs) em 1 mais o length da lista
xs.
length (x:xs) = 1 + length xs
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 4 / 13
Função length
Defina a função length :: [a] -> Int tal que (length xs) devolve o
tamanho da lista xs. Por exemplo,
length [1,2,3,4,6] == 5
A função length transforma
(Caso mais simples) A lista vazia em 0
length [] = 0
(Caso recursivo) A lista não vazia (x:xs) em 1 mais o length da lista
xs.
length (x:xs) = 1 + length xs
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 4 / 13
Função length
1 length :: [a] -> Int
2 length [] = 0
3 length (x:xs) = 1 + length xs
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 5 / 13
Função take
Defina a função take :: Int -> [a] -> [a] tal que (take n xs) devolve os n
primeiros elementos da lista xs. Por exemplo,
take 0 [1,2,3,4,6] == []
take 2 [] == []
take 2 [1,7,8,3] == [1,7]
A função take para
(Caso mais simples) pegar n elementos de uma lista vazia obtenho uma lista
vazia
take n [] = []
(Caso mais simples) pegar 0 elementos de uma lista qualquer obtenho uma
lista vazia
take 0 _ = []
(Caso recursivo) pegar n elementos de uma lista não vazia (x:xs) obtenho
uma lista com x na cabeça e cauda formada pegando (n-1) elementos da
lista xs.
take n (x:xs) = x : take (n-1) xs
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 6 / 13
Função take
Defina a função take :: Int -> [a] -> [a] tal que (take n xs) devolve os n
primeiros elementos da lista xs. Por exemplo,
take 0 [1,2,3,4,6] == []
take 2 [] == []
take 2 [1,7,8,3] == [1,7]
A função take para
(Caso mais simples) pegar n elementos de uma lista vazia obtenho uma lista
vazia
take n [] = []
(Caso mais simples) pegar 0 elementos de uma lista qualquer obtenho uma
lista vazia
take 0 _ = []
(Caso recursivo) pegar n elementos de uma lista não vazia (x:xs) obtenho
uma lista com x na cabeça e cauda formada pegando (n-1) elementos da
lista xs.
take n (x:xs) = x : take (n-1) xs
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 6 / 13
Função take
Defina a função take :: Int -> [a] -> [a] tal que (take n xs) devolve os n
primeiros elementos da lista xs. Por exemplo,
take 0 [1,2,3,4,6] == []
take 2 [] == []
take 2 [1,7,8,3] == [1,7]
A função take para
(Caso mais simples) pegar n elementos de uma lista vazia obtenho uma lista
vazia
take n [] = []
(Caso mais simples) pegar 0 elementos de uma lista qualquer obtenho uma
lista vazia
take 0 _ = []
(Caso recursivo) pegar n elementos de uma lista não vazia (x:xs) obtenho
uma lista com x na cabeça e cauda formada pegando (n-1) elementos da
lista xs.
take n (x:xs) = x : take (n-1) xs
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 6 / 13
Função take
Defina a função take :: Int -> [a] -> [a] tal que (take n xs) devolve os n
primeiros elementos da lista xs. Por exemplo,
take 0 [1,2,3,4,6] == []
take 2 [] == []
take 2 [1,7,8,3] == [1,7]
A função take para
(Caso mais simples) pegar n elementos de uma lista vazia obtenho uma lista
vazia
take n [] = []
(Caso mais simples) pegar 0 elementos de uma lista qualquer obtenho uma
lista vazia
take 0 _ = []
(Caso recursivo) pegar n elementos de uma lista não vazia (x:xs) obtenho
uma lista com x na cabeça e cauda formada pegando (n-1) elementos da
lista xs.
take n (x:xs) = x : take (n-1) xs
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 6 / 13
Função take
1 take :: Int -> [a] -> [a]
2 take n [] = []
3 take0 _ = []
4 take n (x:xs) = x : take (n-1) xs
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 7 / 13
Função map
Defina a função map :: (a->b) -> [a] -> [b] tal que (map f xs) devolve
uma lista formada pela aplicação da função f a cada elemento da lista xs. Por
exemplo,
map (+2) [1,2,3,4] == [3,4,5,6]
map (>3) [1,2,3,4] == [False,False,False,True]
A função map f transforma
(Caso mais simples) uma lista vazia em lista vazia
map f [] = []
(Caso recursivo) uma lista não vazia (x:xs) na lista com (f x) na cabeça e
com a cauda formada aplicando map f na lista xs.
map f (x:xs) = (f x) : map f xs
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 8 / 13
Função map
Defina a função map :: (a->b) -> [a] -> [b] tal que (map f xs) devolve
uma lista formada pela aplicação da função f a cada elemento da lista xs. Por
exemplo,
map (+2) [1,2,3,4] == [3,4,5,6]
map (>3) [1,2,3,4] == [False,False,False,True]
A função map f transforma
(Caso mais simples) uma lista vazia em lista vazia
map f [] = []
(Caso recursivo) uma lista não vazia (x:xs) na lista com (f x) na cabeça e
com a cauda formada aplicando map f na lista xs.
map f (x:xs) = (f x) : map f xs
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 8 / 13
Função map
Defina a função map :: (a->b) -> [a] -> [b] tal que (map f xs) devolve
uma lista formada pela aplicação da função f a cada elemento da lista xs. Por
exemplo,
map (+2) [1,2,3,4] == [3,4,5,6]
map (>3) [1,2,3,4] == [False,False,False,True]
A função map f transforma
(Caso mais simples) uma lista vazia em lista vazia
map f [] = []
(Caso recursivo) uma lista não vazia (x:xs) na lista com (f x) na cabeça e
com a cauda formada aplicando map f na lista xs.
map f (x:xs) = (f x) : map f xs
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 8 / 13
Função map
1 map :: (a->b) -> [a] -> [b]
2 map f [] = []
3 map f (x:xs) = (f x): map f xs
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 9 / 13
Função zip
Defina a função zip :: [a] -> [b] -> [(a,b)] tal que (zip xs ys) devolve
uma lista formada pelas tuplas contendo elementos de ambas as listas que
ocorrem na mesma posição
zip [] [1,2,3] == []
zip [1,2,3] [] == []
zip [1,2,3] [4,5,6,7] == [(1,4),(2,5),(3,6)]
A função zip transforma
(Caso mais simples) uma lista vazia e uma lista qualquer em lista vazia
zip [] _ = []
(Caso mais simples) uma lista qualquer e uma lista vazia em lista vazia
zip _ [] = []
(Caso recursivo) uma lista não vazia (x:xs) e outra lista não vazia (y:ys) em
uma lista com (x,y) na cabeça e com a cauda formada pelo resultado de zip
xs ys
zip (x:xs) (y:ys) = (x,y) : zip xs ys
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 10 / 13
Função zip
Defina a função zip :: [a] -> [b] -> [(a,b)] tal que (zip xs ys) devolve
uma lista formada pelas tuplas contendo elementos de ambas as listas que
ocorrem na mesma posição
zip [] [1,2,3] == []
zip [1,2,3] [] == []
zip [1,2,3] [4,5,6,7] == [(1,4),(2,5),(3,6)]
A função zip transforma
(Caso mais simples) uma lista vazia e uma lista qualquer em lista vazia
zip [] _ = []
(Caso mais simples) uma lista qualquer e uma lista vazia em lista vazia
zip _ [] = []
(Caso recursivo) uma lista não vazia (x:xs) e outra lista não vazia (y:ys) em
uma lista com (x,y) na cabeça e com a cauda formada pelo resultado de zip
xs ys
zip (x:xs) (y:ys) = (x,y) : zip xs ys
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 10 / 13
Função zip
Defina a função zip :: [a] -> [b] -> [(a,b)] tal que (zip xs ys) devolve
uma lista formada pelas tuplas contendo elementos de ambas as listas que
ocorrem na mesma posição
zip [] [1,2,3] == []
zip [1,2,3] [] == []
zip [1,2,3] [4,5,6,7] == [(1,4),(2,5),(3,6)]
A função zip transforma
(Caso mais simples) uma lista vazia e uma lista qualquer em lista vazia
zip [] _ = []
(Caso mais simples) uma lista qualquer e uma lista vazia em lista vazia
zip _ [] = []
(Caso recursivo) uma lista não vazia (x:xs) e outra lista não vazia (y:ys) em
uma lista com (x,y) na cabeça e com a cauda formada pelo resultado de zip
xs ys
zip (x:xs) (y:ys) = (x,y) : zip xs ys
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 10 / 13
Função zip
Defina a função zip :: [a] -> [b] -> [(a,b)] tal que (zip xs ys) devolve
uma lista formada pelas tuplas contendo elementos de ambas as listas que
ocorrem na mesma posição
zip [] [1,2,3] == []
zip [1,2,3] [] == []
zip [1,2,3] [4,5,6,7] == [(1,4),(2,5),(3,6)]
A função zip transforma
(Caso mais simples) uma lista vazia e uma lista qualquer em lista vazia
zip [] _ = []
(Caso mais simples) uma lista qualquer e uma lista vazia em lista vazia
zip _ [] = []
(Caso recursivo) uma lista não vazia (x:xs) e outra lista não vazia (y:ys) em
uma lista com (x,y) na cabeça e com a cauda formada pelo resultado de zip
xs ys
zip (x:xs) (y:ys) = (x,y) : zip xs ys
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 10 / 13
Função zip
1 zip :: [a] -> [a] -> [(a,b)]
2 zip [] _ = []
3 zip _ [] = []
4 zip (x:xs) (y:ys) = (x,y) : zip xs ys
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 11 / 13
Função merge
Defina a função merge :: Ord a => [a] -> [a] -> [a] tal que (merge xs
ys) recebe duas listas ordenadas em ordem crescente e devolve uma lista ordenada
em ordem crescente. Por exemplo,
merge [] [1,2,3] == [1,2,3]
merge [1,2,3] [] == [1,2,3]
merge [1,4,6] [2,3,7] == [1,2,3,4,6,7]
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 12 / 13
Função merge
A função merge transforma
(Caso mais simples) uma lista vazia e uma lista xs na lista xs.
merge [] xs = xs
(Caso mais simples) uma lista ys e uma lista vazia na lista ys.
merge ys [] = ys
(Caso recursivo) uma lista não vazia (x:xs) e outra lista não vazia (y:ys) em
uma lista com x na cabeça se x <= y e com a cauda formada por merge xs
(y:ys).
(Caso recursivo) uma lista não vazia (x:xs) e outra lista não vazia (y:ys) em
uma lista com y na cabeça se x > y e com a cauda formada por merge
(x:xs) ys.
merge (x:xs) (y:ys)
| x <= y = x: merge xs (y:ys)
| otherwise = y: merge (x:xs) ys
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 13 / 13
Função merge
A função merge transforma
(Caso mais simples) uma lista vazia e uma lista xs na lista xs.
merge [] xs = xs
(Caso mais simples) uma lista ys e uma lista vazia na lista ys.
merge ys [] = ys
(Caso recursivo) uma lista não vazia (x:xs) e outra lista não vazia (y:ys) em
uma lista com x na cabeça se x <= y e com a cauda formada por merge xs
(y:ys).
(Caso recursivo) uma lista não vazia (x:xs) e outra lista não vazia (y:ys) em
uma lista com y na cabeça se x > y e com a cauda formada por merge
(x:xs) ys.
merge (x:xs) (y:ys)
| x <= y = x: merge xs (y:ys)
| otherwise = y: merge (x:xs) ys
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 13 / 13
Função merge
A função merge transforma
(Caso mais simples) uma lista vazia e uma lista xs na lista xs.
merge [] xs = xs
(Caso mais simples) uma lista ys e uma lista vazia na lista ys.
merge ys [] = ys
(Caso recursivo) uma lista não vazia (x:xs) e outra lista não vazia (y:ys) em
uma lista com x na cabeça se x <= y e com a cauda formada por merge xs
(y:ys).
(Caso recursivo) uma lista não vazia (x:xs) e outra lista não vazia (y:ys) em
uma lista com y na cabeça se x > y e com a cauda formada por merge
(x:xs) ys.
merge (x:xs) (y:ys)
| x <= y = x: merge xs (y:ys)
| otherwise = y: merge (x:xs) ys
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 13/ 13
Função merge
A função merge transforma
(Caso mais simples) uma lista vazia e uma lista xs na lista xs.
merge [] xs = xs
(Caso mais simples) uma lista ys e uma lista vazia na lista ys.
merge ys [] = ys
(Caso recursivo) uma lista não vazia (x:xs) e outra lista não vazia (y:ys) em
uma lista com x na cabeça se x <= y e com a cauda formada por merge xs
(y:ys).
(Caso recursivo) uma lista não vazia (x:xs) e outra lista não vazia (y:ys) em
uma lista com y na cabeça se x > y e com a cauda formada por merge
(x:xs) ys.
merge (x:xs) (y:ys)
| x <= y = x: merge xs (y:ys)
| otherwise = y: merge (x:xs) ys
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 13 / 13
Função merge
A função merge transforma
(Caso mais simples) uma lista vazia e uma lista xs na lista xs.
merge [] xs = xs
(Caso mais simples) uma lista ys e uma lista vazia na lista ys.
merge ys [] = ys
(Caso recursivo) uma lista não vazia (x:xs) e outra lista não vazia (y:ys) em
uma lista com x na cabeça se x <= y e com a cauda formada por merge xs
(y:ys).
(Caso recursivo) uma lista não vazia (x:xs) e outra lista não vazia (y:ys) em
uma lista com y na cabeça se x > y e com a cauda formada por merge
(x:xs) ys.
merge (x:xs) (y:ys)
| x <= y = x: merge xs (y:ys)
| otherwise = y: merge (x:xs) ys
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 5 - Definição recursiva 13 / 13