Haskell: Recursividade

Fala aí galera, hoje peguei firme no estudo e estou escrevendo esse post com o Vim! :D

Vou falar mais um pouco de Haskell e o assunto hoje é Recursividade.

A recursividade é a definição de uma subrotina (função ou método) que pode invocar a si mesma (Definição Recursividade). A Matéria sobre Recursividade da Wikipédia está impecável, não deixe de ler.

Onde isso é útil?
Imagine, você precisa calcular a soma dos n primeiros números. Ou seja, precisa escrever uma função que receberá como parâmetro um número n, você terá que somar esse número n a todos os seus antecessores, para que não seja feito através da iteração, podemos usar a recursão.

E a idéia é simples, vamos as definições:
soma (n) = { 1                         : n = 1
                  { soma (n - 1) + 1 : n > 1

soma 10 = 1+2+3+4+5+6+7+8+9+10 = 55

Poxa, mas como minha função sabe onde deve parar?
Devemos definir um aterramento, ou seja, um ponto onde a função deva parar.(Uma Guarda!)

De acordo com a definição matemática de indução, registrada acima, para n = 1, temos como resultado o número 1, para n > 1, nós invocamos novamente a função soma.

Vamos codar, para isso crie um novo arquivo em seu diretório favorito, de o nome de soma_recursividade.hs e digite em seu interior:

soma Int -> Int
soma 1 = 1
soma n = soma (n-1) + n

Ou seja, caso nosso n = 1, a função soma 1, entra em ação e retorna 1. Caso n > 1, a função soma(n), entra em ação, fazendo uso de si mesma para executar a tarefa de soma, isso se chama recursividade.

Podemos compreender o que o Hugs faz, interpretando essa função como escadaria da recursividade, quer ver?

soma 5
= (soma 4) + 5
= ((soma 3) + 4) + 5
= (((soma 2) + 3) + 4 ) + 5
= ((((soma 1) + 2) + 3) + 4) + 5

Agora,o seu interpretador resolverá a função de acordo com as prioridades:

= ((((1) + 2) + 3) + 4) + 5
= (((3) + 3) + 4) + 5
= ((6) + 4) + 5
= (10) + 5
= 15

Teste você mesmo, caminhe até o local do arquivo e:
hugs soma_recursividade.hs

Main> soma 10
15

Pronto! Simples? Talvez meio complicado para compreender de início, mas quando entra na cabeça, parece até simples. rs

Vou até deixar um exercício, ou melhor, dois!

Exercício 3:
O que acha de aprender a usar o Vi ? ou o Vim (Vi improved)?
É simples, poderoso e um software livre!

Eu treinei com esse aí:
Tutorial Básico Vim

Logo, quando eu estiver mais confortável, escrevo um post a respeito do Vim.

Exercício 4:
Crie uma função, em Haskell, que receba um inteiro como parametro e calcule o seu fatorial.

Vamos as definições matemáticas:
O Fatorial, para quem não lembra, é o número corrente multiplicado pelo fatorial de seu antecessor.
fatorial (n) = { 1 : n = 0
                    { fatorial (n - 1) * n  : n > = 1

Bom, se rolar alguma dúvida, não se esqueçam de comentar abaixo ou email-me: abner.terribili@gmail.com. A resposta para o exercicio 4 está no meu GitHub, nome exercicio_4.hs.

Até mais galera!