Ir para o conteúdo
leia

recursão terminal

Mensagens Recomendadas

leia

boa noite ,

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.

eu fiz assim :

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
True

Me pode alguem dizer se faz favor se fiz bem ou que esta errado . baralho bastante a recursão terminal. :( :( :(

Agradeço a ajuda.

Editado por leia

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
thoga31

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?


Knowledge is free!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
leia

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.

Obrigada!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
thoga31

Nunca ouvi falar de "recursão terminal", define-me este conceito.

A tua função cumpre na perfeição o enunciado.


Knowledge is free!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
leia

vou tentar por um exemplos onde e considerada a recursão terminal.

se tiver

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 . :(

Editado por leia

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
thoga31

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!!


Knowledge is free!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
leia

Pois.....

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!

obgd

Alinhei as guards a bocadinho em cima. ;)

Editado por leia

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
thoga31

Agora estão bem alinhadas :D

Outra resolução...?

existe :: (Eq a) => a -> [a] -> Bool
existe n = foldl (\curr x -> curr || n == x) False

Nota: troquei os argumentos.


Knowledge is free!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Rui Carlos

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

g x | x==0 = 1
   | 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).

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
motherFFH

vou tentar por um exemplos onde e considerada a recursão terminal.

se tiver

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 

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:

(define (g x)
 (if (= x 0)
  1
  (+ 1 (g (- x 1)))))

O compilador pode produzir o seguinte código:

g:
 pop r1	 ; x
 xor r0,r0  ; resultado
loop:
 cmp r1,r1
 jz ret
 inc r0  ; 1+g(..)
 dec r1 ;
 jmp loop ; g(x-1)
ret:
 inc r0
 ret

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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Rui Carlos

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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
motherFFH

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

g = g' 0
 where g' acc x | x == 0 = acc + 1
		 | otherwise = g' (acc+1) (x-1)

em vez do original

g x | x==0 = 1
| otherwise = 1 + g (x-1)

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.