Jump to content
leia

recursão terminal

Recommended Posts

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.

Edited by leia

Share this post


Link to post
Share on other 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!

Share this post


Link to post
Share on other 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!

Share this post


Link to post
Share on other 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!

Share this post


Link to post
Share on other 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 . :(

Edited by leia

Share this post


Link to post
Share on other 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!

Share this post


Link to post
Share on other 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. ;)

Edited by leia

Share this post


Link to post
Share on other 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!

Share this post


Link to post
Share on other sites
leia

Muito obrigada!!!!

foldr e foldl vou ter que estudar muito ainda !!! Mas percebi a função

Share this post


Link to post
Share on other 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).

Share this post


Link to post
Share on other 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.

Share this post


Link to post
Share on other 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.

Share this post


Link to post
Share on other 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)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.