recursão terminal - Haskell - Portugal-a-Programar
By leia, November 5, 2013 in Haskell
Estou as voltas com a recursão terminal quando quero definir a função recursiva existe :: Eq a => [a] -> a -> Bool que decide se o elemento dado como segundo argumento existe na lista dada como primeiro argumento.
existe1 :: Eq a => [a] -> a -> Bool
existe1 [] n = False
existe1 (x:xs) n | x == n = True
| otherwise = existe1 xs n
e obtive este resultado :
Main> existe1 [1,2,3,4,5] 3
Me pode alguem dizer se faz favor se fiz bem ou que esta errado . baralho bastante a recursão terminal. :(
Edited November 5, 2013 by leia
Tens de indentar bem as guards, elas devem estar, neste caso, alinhadas.
Ora pensa lá: a função tem de verificar se um elemento existe numa lista, e obtiveste esse output. É o esperado?
Eu percebi que o elemento dado como segundo argumento neste caso n existe na lista dada como primeiro argumento neste caso [].
Pela minha lógica penso que em cima consegui o que era pedido.
Estou errada ????? entendi mal o pedido???
A minha maior duvida entre as outras que coloquei e se usei a recursão terminal pk não consigo distinguir isso. Comecei a muito pouco tempo com haskell e vou fazendo funções para aprender a programação funcional.
Nunca ouvi falar de "recursão terminal", define-me este conceito.
A tua função cumpre na perfeição o enunciado.
vou tentar por um exemplos onde e considerada a recursão terminal.
g x | x==0 = 1
| otherwise = g(x-1) --consid. recursão terminal pk so faz uma operção ao seguir do =
se tiver |otherwise= 1+g(...) -- nao e consid.rec.terminal pk faz mais que uma operação
Ha quem diz que a recursão terminal e uma caracteristica do codigo e não da execução.
Nao sei explicar melhor que isso .
Bem, para inventarem conceitos estamos por aí... qualquer dia o livro de definições informáticas é maior do que o de anatomia, fisiologia e histologia. Adiante.
Se entendi bem o conceito, então a tua função é recursiva terminal.
E alinha as guards!!
realmente e verdade.!!
Já agora ha mais alguma maneira de resolver este enunciado ? tipo mais algum exemplo de resolução para eu ver e analisar!
Alinhei as guards a bocadinho em cima.
Agora estão bem alinhadas
Outra resolução...?
existe :: (Eq a) => a -> [a] -> Bool
existe n = foldl (\curr x -> curr || n == x) False
Nota: troquei os argumentos.
foldr e foldl vou ter que estudar muito ainda !!! Mas percebi a função
Por recursão terminal querem dizer tail recursive.
E sim, a tua função é recursiva terminal, pois devolve imediatamente o resultado da chamada recursiva, sem fazer mais nenhuma operação com esse resultado. Atenção que isto é diferente de só fazer uma operação. Em
| otherwise = g(x-1)
g(x-1) está a fazer duas funções/operações (uma subtracção, e uma chamada à função g), mas a chamada à função g é a última coisa a ser executada antes da função retornar o resultado.
Já agora, este tipo de funções recursivas é importante, pois podem ser optimizadas de modo a evitar problemas com o crescimento da call stack que é necessário manter (evitando-se assim potenciais stack overflows).
Sim isso mesmo Rui Carlos.
Viva. O segundo caso também é tail recursion em minha opinião.
Façamos a seguinte conversão para scheme, para se perceber melhor a AST:
(+ 1 (g (- x 1)))))
O compilador pode produzir o seguinte código:
pop r1	 ; x
xor r0,r0  ; resultado
cmp r1,r1
inc r0  ; 1+g(..)
jmp loop ; g(x-1)
i.e. a recursão foi eliminada, sendo convertida para um while.
Nota: isto é apenas para reflexão, sigam sempre as normas que vos ensinaram.
motherFFH, penso que estás a considerar que dois conceitos são equivalentes, quando um é apenas um caso particular do outro. Os algoritmos tail recursive são algoritmos em que é possível remover a chamada recursiva facilmente, mas o facto de a conseguires remover, não significa que o algoritmo seja tail recursive.
Em geral os algoritmos que só têm uma chamada recursiva podem ser convertidos em ciclos, mas a transformação necessária nem sempre será óbvia, e, mais importante, há uma série de pormenores a ter em conta para garantir que o resultado não é afectado (se tens uma operação associativa, se sabes qual é o elemento neutro da operação, etc.). É que na transformação que fizeste estás a inverter a ordem dos cálculos (o que nesse caso não é problema, visto que fica sempre 1+1+1+...).
Um exemplo em que isso não acontece: em C, o Clang só te remove a chamada recursiva dessa função se usares inteiros para o resultado. Se tiveres floats, já não faz isso (a soma de floats não é associativa, e já é bem mais complicado garantir que a troca da ordem das operações não vai ter interferência no resultado). Numa função tail recursive consegues remover a chamada recursiva sem alterar a ordem de execução das operações, daí ser mais fácil garantir que o resultado não é alterado.
Sim, acho que tens razão. No fundo a minha implementação em pseudo-asm converte o código da função para um equivalente funcional, usando um acumulador. I.e. isto