• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Aqua Costa

Recursividade?

11 mensagens neste tópico

Estive a ler uns artigos sobre recursividade e todos dizem que é um pouco lento e ocupa muita memória stack...

Afinal quais são as vantagens de utilizar recursividade?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Para conseguires ler todos os conteúdos de um directório, e se ele tiver pastas, o conteúdo das mesmas, e se essas tiverem pastas dentro, o conteúdo das mesmas, etc. É para isso que eu a utilizo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Se conseguires resolver um problema recursivo sem recursividade estás livre de o fazer. O problema é que as soluções ficam tão complexas que o trabalho extra não vale a pena (além de terem que usar uma stack auxiliar e gastarem a mesma memória).

Há vários problemas que são tipicamente recursivos.

Por exemplos os números de fibonacci: (apesar de poderes fazer iterativo sem stack)

fib[0] = fib[1] = 0

fib[n] = fib[n-1] + fib[n-2]

Fica um desafio: faz um programa que leia um número N, e imprima todas as permutações de N elementos.

Exemplo:

Input:

3

Output:

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Estive a ler uns artigos sobre recursividade e todos dizem que é um pouco lento e ocupa muita memória stack...

Mais ou menos. Isso é verdade em linguagens que não suportam TCO. Se suportar TCO e a recursividade estiver bem implementada, isto é, feito de forma a tomar partido da optimização, o tempo/memória da stack irá ser constante. Ainda à pouco tempo, houve uma grande discussão na web relativo a Python não suportar TCO. Em que o próprio Guido a recusar a inclusão.

Afinal quais são as vantagens de utilizar recursividade?

A principal vantagem, é que em certos algoritmos é mais fácil implementar recursivamente do que iterativamente. E normalmente também é mais fácil raciocinar se um dado algoritmo está correcto.
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Só para acrescentar um pouco:

Existem problemas recursivos o que, basicamente, significa que a sua formulação é recursiva, ou seja, o n-ésimo valor/estado depende de estados anteriores. Tens também uma condição inicial que te vai dar a condição de paragem. No caso da formulação recursiva da sequencia de Fibonacci é fib[0] = fib[1] = 0.

Agora, estes problemas recursivos e a sua implementação podem gerar processos recursivos ou iterativos.

Não tens de ter medo de problemas recursivos mas sim de implementações que geram processos recursivos. Assim, deves tentar evitá-los e procurar formas de os fazer a gerar processos iterativos (ou outros métodos como programação dinâmica, etc). Um bom exercício é tentares fazer duas implementações recursivas do factorial, uma a gerar processos iterativos e outra a gerar processos recursivos. Depois podes comparar a eficiência :D  (se tiveres dificuldade posso dar uma ajuda)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não tens de ter medo de problemas recursivos mas sim de implementações que geram processos recursivos. Assim, deves tentar evitá-los e procurar formas de os fazer a gerar processos iterativos (ou outros métodos como programação dinâmica, etc). Um bom exercício é tentares fazer duas implementações recursivas do factorial, uma a gerar processos iterativos e outra a gerar processos recursivos. Depois podes comparar a eficiência :D  (se tiveres dificuldade posso dar uma ajuda)

Só uma correcção. Como disse antes só se tem de ter cuidado de problemas recursivos em linguagens que não suportam TCO. Numa linguagem com TCO uma implementação iterativa e recursiva são a mesma coisa.

Programação dinâmica não é uma substituição de recursividade. É tão possível elaborar algoritmos dinâmicos iterativos como recursivos. Aliás se DP fosse apenas possível em algoritmos iterativos então linguagens que apenas suportam recursividade (Haskell por exemplo) não seria possível DP, o que é falso.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Só uma correcção. Como disse antes só se tem de ter cuidado de problemas recursivos em linguagens que não suportam TCO. Numa linguagem com TCO uma implementação iterativa e recursiva são a mesma coisa.

Estava a falar de programação em termos genéricos e como tal achei pertinente. De resto acho uma questão interessante de se saber em termos académicos. E programação, como eu a vejo, é um pouco mais do que codificar.

Programação dinâmica não é uma substituição de recursividade.

Não sei se passei a ideia erradamente mas o que pretendia dizer era que em certos problemas recursivos (estou a falar do problema e não da implementação) se pode usar DP para optimizar, tal como outros métodos...

Aliás se DP fosse apenas possível em algoritmos iterativos então linguagens que apenas suportam recursividade (Haskell por exemplo) não seria possível DP, o que é falso.

Não consigo perceber a ligação desta última afirmação com o meu post ou com qualquer outra parte deste tópico. Queres explicar melhor?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O que queria dizer é que DP é independentemente da implementação iterativa ou recursiva, dá em ambas.

Depois, para reforçar esta afirmação, referi que existem linguagens que só permitem recursividade, não oferecem qualquer maneira de implementar um algoritmo iterativo, no é possível DP.

Mas parece que te entendi mal. Pensei que estavas a dizer que DP só era possível em implementações iterativas.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Só uma ressalva betovsky, provavelmente já sabes isso, mas mesmo que uma linguagem suporte TCO não significa que todas as funções recursivas sejam transformadas em iterativas.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Se suportar TCO e a recursividade estiver bem implementada, isto é, feito de forma a tomar partido da optimização, o tempo/memória da stack irá ser constante.

:D

De salientar que transformar uma(s) função(ões) recursiva(s) para a sua forma óptima é muitas vezes uma passo trivial. E transformar para o modelo iterativo às vezes não é tão simples.

Por exemplo recursividade sobre 2 funções. Função f chama função g em que esta chama a função f.

0

Partilhar esta mensagem


Link 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