Haskell aula 07

Prévia do material em texto

*
Haskell aula 07
Perigos da recursão
Prof. Msc Aurélio Andrade de Menezes Júnior.
*
Perigos da recursão
As funções recursivas em Haskell merecem uma atenção especial.
Como se observa uma função recursiva é uma função que se chama a si mesma, e quase todas as construções em Haskell são recursivas, pois necessitam de algum tipo de repetição.
Praticamente em toda a função recursiva existe o conceito de aterramento, o qual deve sempre vir antes da linha que faz a chamada da função recursiva geral.
*
Perigos da recursão
Caso se inverta a sequencia destas linhas, uma sequencia infinita de chamadas vai efetivamente ocorrer, se os critérios de parada não estejam bem-definidos.
Uma função bem definida é aquela que possui um número de passos finitos, em que seus n aterramentos sempre se encontram antes da função recursiva geral.
*
Perigos da recursão
O exemplo a seguir descreve a função mult_7, cujo objetivo é retornar o número de múltiplos de 7 encontrados no intervalo de 0 até o número informado pelo usuário.
mult_7 3 = 0 mult_7 4 = 0
mult_7 2 = 0 mult_7 1 = 0
mult_7 5 = 0 mult_7 7 = 1
mult_7 6 = 0 mult_7 x = 1 + mult_7 (x-7)
Execução:
Main> mult_7 9 Main>mult_7 18
1 2
Main> mult_7 21 Main>mult_7 3
3 0 
*
Perigos da recursão
mult_7 3 = 0 mult_7 1 = 0
mult_7 5 = 0 mult_7 7 = 1
mult_7 6 = 0 mult_7 x = 1 + mult_7 (x-7)
mult_7 4 = 0 mult_7 2 = 0
Execução:
Main> mult_7 4 Main>mult_7 10
0 1
Main> mult_7 9
ERROR: control stack overflow 
*
Perigos da recursão
mult_7 3 = 0 mult_7 1 = 0
mult_7 2 = 0 mult_7 7 = 1
mult_7 5 = 0 mult_7 x = 1 + mult_7 (x-7)
mult_7 4 = 0
Execução:
Main> mult_7 8 Main>mult_7 15
1 2
Main> mult_7 13
ERROR: control stack overflow 
*
Perigos da recursão
No primeiro exemplo o aterramento multiplo_7 2=0 foi colocado depois da função recursiva geral mult_7 x = 1 + mult_7 (x-7), a função continua funcionando.
Já no segundo exemplo ocorre o mesmo erro ao chamar o aterramento mult_7 x = 1 + mult_7 (x-7), pois o mesmo foi omitido.
*
Perigos da recursão
Uma solução alternativa e prática é a utilização de guardas (‘|’), onde o exemplo anterior deve ser reescrito da seguinte maneira:
mult_7 7 = 1 
mult_7 x = |(x>=1) && (x<= 6) = 0
 | otherwise 1 + mult_7 (x-7)
Execução
Main> mult_7 70 Main>mult_7 1
10 0
Main> mult_7 4 Main> mult_7 7
0 1
0
*
Perigos da recursão
Uma guarda é uma condição lógica a ser verdadeira, para que a definição da função seja executada. A condição otherwise aceita qualquer condição, ou seja, qualquer condição não satisfeita nas guardas anteriores é aplicada a condição otherwise.
*
Perigos da recursão
As guardas são montadas da seguinte maneira:
Função parametro_1 parametro_2 ...
 | guarda_1 = expressão_1
 | guarda_2 = expressão_2
 ......
 | otherwise = expressão_n
Uma expressão pode assumir n parâmetros, n guardas e suas respectivas expressões a serem realizadas e um otherwise que abrange as demais condições existentes não declaradas
*
Dúvidas