[Haskell Aula 03] Recursividade

[VictorCacciari 42]

Aula 03 -> Recursividade

 

Boas pessoal!

Encontrei um tempinho livre e resolvi escrever mais uma aula.

E hoje vamos falar do assunto mais importante em programação funcional, recursividade.

 

Definição:

Recursividade: Se você ainda não entendeu, ver Recursividade.

 

Definição formal:

Na matemática e na ciência da computação, a recursão especifica (ou constrói) uma classe de objetos ou métodos (ou um objeto de uma certa classe) definindo alguns poucos casos base ou métodos muito simples (freqüentemente apenas um), e então definindo regras para formular casos complexos em termos de casos mais simples.

 

Por exemplo, segue uma definição recursiva da ancestralidade de uma pessoa:

 

* Os pais de uma pessoa são seus antepassados (caso base);

* Os pais de qualquer antepassado são também antepassados da pessoa em consideração (passo recursivo).

 

É conveniente pensar que uma definição recursiva define objetos em termos de objetos “previamente definidos” dessa mesma classe que está sendo definida.

 

Definições como esta são frequentemente encontradas na matemática, por exemplo, a definição formal dos números naturais diz que 0 (zero) é um número natural, e todo número natural tem um sucessor, que é também um número natural.

 

(fonte: Wikipedia)

 

A recursividade na programação funciona de uma forma ligeiramente diferente da recursão na matemática.

Vamos definir por exemplo a seguinte função:

f :: Int -> Int
f 0 = 10
f x = (f (g x))

Temos o caso de paragem, quando o primeiro argumento é zero, e temos o passo recursivo, que depende de uma outra função 'g'.

Essa definição funciona APENAS se 'g' transformar 'x' em algo mais próximo do caso de paragem.

Isso é importante!

No passo recursivo temos sempre que 'diminuir' as coisas, evitando assim entrar numa recursão infinita.

 

 

Ja falamos um pouco sobre listas, vamos então definir funções que trabalham com listas:

//Faz o somatório de uma lista
soma :: [Int] -> Int
soma [] = 0
soma (h:t) = h + (soma t)


//Faz o produtório de uma lista
mult :: [Int] -> Int
mult [] = 1
mult (h:t) = h * (mult t)

estaNaLista :: [Int] -> Int -> Bool
estaNaLista [] _ = False
estaNaLista (h:t) n = if n == h then True
                                else estaNaLista t n

//Pega os 'n' primeiros items de uma lista
pegarPrimeiros :: [Int] -> Int -> [Int]
pegarPrimeiros [] _ = []
pegarPrimeiros _ 0 = []
pegarPrimeiros (h:t) n = h : (pegarPrimeiros t (n-1))
				

A função 'estaNaLista', que checa se um elemento está contido na lista, pode ser definida com uma sintaxe diferente:

estaNaLista :: [Int] -> Int -> Bool
estaNaLista [] _ = False
estaNaLista (h:t) n | n == h = True
                    | otherwise = estaNaLista t n

E dessa forma impomos condições, é como as funções por ramos na matemática.

A vantagem é que podemos impor quantas condições quisermos, e especificar uma expressão para cada condição, o Haskell executará a expressão da condição que for satisfeita primeiro.

(Exercício: definir 'estaNaLista' sem usar if nem condições)

 

Na aula sobre listas, vimos algumas formas de definir listas, e em Haskell podemos inclusive definir listas infinitas.

Por exemplo, escrevam o seguinte comando no GHCi: '[1..]'

Nunca mais acaba, não é?

Agora tente: 'pegarPrimeiros [1..] 10'

 

o.O

No mínimo estranho...

Pedimos uma lista infinita para o Haskell e ele consegue fazer a computação?

Isso chama-se lazy-evaluation, o Haskell só avalia as coisas quando são estritamente necessárias.

Vamos estudar o funcionamento da função 'pegarPrimeiros' com os mesmos parametros que passamos acima:

//Pega os 'n' primeiros items de uma lista
pegarPrimeiros :: [Int] -> Int -> [Int]                
pegarPrimeiros [] _ = []                               // ramo A
pegarPrimeiros _ 0 = []                                // ramo B
pegarPrimeiros (h:t) n = h : (pegarPrimeiros t (n-1))  // ramo C

pegarPrimeiros [1..] 10 //Vamos pelo ramo C, onde 'h' vale 1, 't' vale [2..] e 'n' vale 10.
1 : (pegarPrimeiros [2..] 9) //Vamos novamente pelo ramo C...
1 : ( 2 : (pegarPrimeiros [3..] 8)) //outra vez...
1 : ( 2 : ( 3 : (pegarPrimeiros [4..] 7))) //Após algumas vezes nisso...
1 : ( 2 : ( 3 : ( 4 : ( 5 : ( 6 : ( 7 : ( 8 : ( 9 : ( 10 : (pegaPrimeiros [11..] 0)))))))))) //Agora vamos com o ramo B
1 : ( 2 : ( 3 : ( 4 : ( 5 : ( 6 : ( 7 : ( 8 : ( 9 : ( 10 : [] )))))))))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

E notem que o Haskell não avalia a lista infinita, apenas pega items de lá quando é preciso.

(nota: Comentários em Haskell são com '--' não com '//', mas utilizei '//' para aparecer como comentário no código.)

 

 

Bom, alguma coisa sobre recursividade está ai.

Ja temos as bases para começar a entrar em coisas mais interessantes! =D

 

Exercícios:

Defina as seguintes funções:

//Retorna o fatorial de um número
fatorial :: Int -> Int

//Retorna o n-ésimo número da sequencia de fibonacci DICA: crie funções auxiliares.
fibonacci :: Int -> Int

//Multiplica todos elementos de uma lista por 'n'
multPor :: [Int] -> Int -> [Int]

//Calcula um número 'x' elevado à potência 'y'
potencia :: Int -> Int -> Int

Desafio:

A função que calcula a potência de um número pode ser mais eficiente...

Quantas multiplicações são geralmente feitas para computar 5^10 ??

nove multiplicações.

Mas, note que:

5^10 = (5^5)^2 = (5*(5^4))^2 = (5*((5^2)^2))^2

E, com essa forma simplificada são efetuadas apenas 4 multiplicações. (5^2 = 5*5 --> uma multiplicação)

 

O desafio consiste em implementar esse método mais eficiente.

 

Bom, por hoje é só!

Abraços pessoal!