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

Sven

Recursão, quem usa ?

Recursão, quem usa ?   32 membros votaram

  1. 1. Recursão, quem usa ?

    • sempre que possivel
      9
    • prefiro os loops
      5
    • sei o que é mas raramente uso
      9
    • nunca ouvi falar
      9

Please inicie sessão ou registe-se para votar.

30 mensagens neste tópico

Viva

Estou a fazer um pequeno estudo sobre técnicas de programação

Gostava que me ajudassem com esta votação e respondessem sinceramente.

Quantos sabemo que é e programam recorrendo à recursão ?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Acho que não é uma questão de preferência, mas de necessidade. Há problemas que se resolvem mais fácil ou eficientemente com recursão, e outros com iteração.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

ok, o teu ponto é válido,

mas a questão é tendo a hipótese de usar recursão quantos a usam, e quantos preferem usar um loop

O mesmo se passa com as classes podes criar uma classe para encapsular o acesso à base de dados ou podes repetir o código

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

dependendo do objectivo do programa posso usar ou não recursividade.

quando estou a usar C/C++, MatLab, Java, PHP, etc. uso quase sempre ciclos. é claro que operações como travessias de árvores recorrendo a ciclos, embora possíveis, dão o dobro do trabalho (e os ganhos em eficiência não devem ser muitos...), e aí normalmente fico-me pela recursividade.

em linguagens como Haskell ou Prolog acho que nem existem ciclos, por isso temos que recorrer à recursividade. mesmo em VDM onde já existem ciclos, como o objectivo quando uso essa linguagem é fazer programas formalmente correctos, não uso ciclos.

resumindo, os ciclos são bons quando queremos programas eficientes, a recursividade é melhor quando queremos apenas modelar os problemas.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Recursividade sempre que possivel nos primeiros estagios da construção do software,e quando simplifica a vida ao programador.

Se optimização for um passo muito importante, então a recursividade é um local a analisar.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Nem mais, vou-me abster de votar porque a pergunta não faz sentido para mim.

Recursividade (ou recursão) não é uma preferência, mas uma necessidade. Um algoritmo iterativo é mais rápido do que um algoritmo recursivo, mas normalmente consome mais código e tempo e é portanto mais sujeito a erros do programador. Recursividade facilita (muito) o nosso trabalho.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu concordo com o warrior, excepto numa parte. Uma aboradegem recursiva é muito mais económica que uma não recursiva.

A pergunta nao faz sentido. Um programador ao escrever um programa implementa um algoritmo. O algoritmo ou é recursivo ou nao é. Não se trata de usar ciclos ou nao, os ciclos não são uma alternativa a recursividade.

Por exemplo, implementa aí o quicksort numa linguagem qualquer sem usares recursividade... n consegues.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Por exemplo, implementa aí o quicksort numa linguagem qualquer sem usares recursividade... n consegues.

será que não? por acaso nunca tentei, mas quase que apostava que é possível. podes fazer travessias em profundidade/largura num grafo recorrendo a stacks/queues, o quicksort resume-se à travessia de uma árvore, que é um caso particular de um grafo, por isso tenho quase a certeza que é possível implementá-lo recorrendo a ciclos. agora será que o algoritmo iria ser mais eficiente? provavelmente não, por tua ias simular aquilo que a máquina faz, ou seja, em vez de ser a máquina a tratar da stack, eras tu a fazê-lo.

EDIT: a máquina não pode recorrer à recursividade, ela apenas executa instruções assembly que está constantemente a ler, bastava fazer uma simulação daquilo que a máquina faz para um algoritmo recursivo para obter a sua versão iterativa.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Nem mais, o facto de o compilador converter qualquer código (recursivo ou não) em instruções Assembly (iterativas) mostra que a recursividade pode ser substituída. A questão é se compensa ou não..

Eu concordo com o warrior, excepto numa parte. Uma aboradegem recursiva é muito mais económica que uma não recursiva.

Económica em que aspecto? Velocidade? Memória? Código?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

EDIT: a máquina não pode recorrer à recursividade, ela apenas executa instruções assembly que está constantemente a ler, bastava fazer uma simulação daquilo que a máquina faz para um algoritmo recursivo para obter a sua versão iterativa.

Ora... discordo. Quando fazes um algoritmo recursivo, o compilador cria código assembly que coloca os parâmetros no stack e utiliza a instrução call. É diferente de um algoritmo iterativo em que não há cópias para o stack e são utilizados jmps.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Qualquer código feito recursivamente é possível ser feito com loops, a recursividade de grosso modo é apenas a utilização de um método como se este se tratasse de um loop, o código por trás é bastante semelhante, a diferença é apenas aquela apontada pelo TheDark.

EDIT: aquele voto solitário no "prefiro loops" é meu, parece que estou sempre contra a maré  ;) viva as minorias!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

EDIT: a máquina não pode recorrer à recursividade, ela apenas executa instruções assembly que está constantemente a ler, bastava fazer uma simulação daquilo que a máquina faz para um algoritmo recursivo para obter a sua versão iterativa.

Ora... discordo. Quando fazes um algoritmo recursivo, o compilador cria código assembly que coloca os parâmetros no stack e utiliza a instrução call. É diferente de um algoritmo iterativo em que não há cópias para o stack e são utilizados jmps.

o que é que a máquina faz? lê instruções iterativamente não? essas instruções em podem ser a tradução de um algoritmo recursivo. o processador (máquina) funciona de forma iterativa.

tu podes fazer um programa que simula a máquina e que executa o código fonte do programa. o programa seria sequencial pois a única coisa que faria era ler instruções. um call resume-se a passar meia-dúzia de endereços para uma stack, colocar lá os argumentos e a fazer um jump. tu podes perfeitamente manter essa stack e passas a ter um algoritmos iterativo (mas que na realidade faz o mesmo que o recursivo).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Nem mais, o facto de o compilador converter qualquer código (recursivo ou não) em instruções Assembly (iterativas) mostra que a recursividade pode ser substituída. A questão é se compensa ou não..

Eu concordo com o warrior, excepto numa parte. Uma aboradegem recursiva é muito mais económica que uma não recursiva.

Económica em que aspecto? Velocidade? Memória? Código?

Estava-me a referir ao código. Pelo que percebi disseste que uma implementação não recursiva necessita de menos código. Eu discordo plenamente, os algoritmos recursivos primam pela elegancia.

Tipicamente um algoritmo recursivo tem uma impleentação super-resumida em termos de código.

Epa... eu estou de acordo com o thedark. Isto é uma questao de algoritmia, não interessa como é que os computadores funcionam ou o aspecto do código ou como este é compilado. Não está aqui em discussão ( penso eu, posso estar enganado ) se a melhor forma de implementar recursividade é usando a tradicional função que faz uma chamada a si própria.

Use-se o compilador que se usar, um algoritmo recursivo é um algoritmo que, a dada altura submete dados calculados por si ao procedimento que os ogirinou.

Por exemplo: imaginemos que eu escrevo um documento e quero que este esteja apresentavel.

Posso por exemplo: le-lo e ir corrigindo o que encontro mal: ortografia, pontuação, apresentaçao, estrutura.

A seguir faço o mesmo ( ao mesmo documento ) pois acho que ainda posso melhora-lo

outra vez,

outra

outra

até ficar satisfeito com a qualidade deste ( amiha condição de paragem )

Isto seria uma uma abordagem recursiva do problema, uma diferente seria:

primeiro corrigo a ortografia com o máximo cuidado

depois a estrutura

depois a pontuação

apresentação

( inserir qq coisa aqui )

está pronto!

Isto seria um método não recursivo

O primeiro métido é conceptualmente muito mais simples, mas pode ser mais dispendioso em termos de recursos.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Epa... eu estou de acordo com o thedark. Isto é uma questao de algoritmia, não interessa como é que os computadores funcionam ou o aspecto do código ou como este é compilado. Não está aqui em discussão ( penso eu, posso estar enganado ) se a melhor forma de implementar recursividade é usando a tradicional função que faz uma chamada a si própria.

o que estava em causa era se podemos ou não ter sempre uma versão iterativa de um algoritmo recursivo. no caso concreto do quicksort (ou das travessias de árvores/grafos) podemos converter o algoritmo recursivo para iterativo facilmente. em qualquer outro algorimto basta pensarmos como é que ele é traduzido para a máquina para sabermos como o converter.

quando referiste que os ciclos não são uma alternativa à recursividade, estavas errado, o que eu tentei mostrar foi isso mesmo, usando a forma como o código é executado apenas como justificação.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Recursão não me parece uma boa maneira de codar, pelo menos para certos algoritmos, em que pode tornar-se potencialmente lento, por esgotar bastante stack...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

zoiks... epa... n acredito nas respostas que este tópic está a ter.

Alguem me escreve aqui uma versão do quicksort sem ser recursiva? Ou melhor ainda, alguem me escreve aqui numa linguagem qualquer um algoritmo de ordenação não recursivo que seja mais rápido que o quicksort?

Tenho sudoku solver parado a meio pois ainda n percebi como fazer tail-backtracking. Se alguem  souber um algoritmo mais simples e mais rapido que nao seja recursivo tambem agradecia.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Um algoritmo iterativo é mais rápido do que um algoritmo recursivo, mas normalmente consome mais código e tempo e é portanto mais sujeito a erros do programador.

Eu disse claramente que um algoritmo iterativo (normalmente) consome mais código e é menos elegante.

Quanto ao quicksort, é fácil fazer-se uma versão iterativa dele, se usares uma stack codada por ti mesmo.

Só tens que simular o comportamento do algoritmo recursivo com um loop enquanto vais armazenando as chamadas anteriores num pilha.

Podes ver um quicksort iterativo aqui:

http://en.wikipedia.org/wiki/Quicksort#Iterative_version

De resto, consegues converter qualquer algoritmo recursivo com maior ou menor dificuldade num algoritmo iterativo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
zoiks... epa... n acredito nas respostas que este tópic está a ter.

o que queres dizer com isto? achas que há algoritmos que não podem ser implementados de forma iterativa?

Ou melhor ainda, alguem me escreve aqui numa linguagem qualquer um algoritmo de ordenação não recursivo que seja mais rápido que o quicksort?

daqui a alguns dias (espero que poucos) devo responder-te a esta questão (para o caso da ordenação de inteiros).


quanto à versão iterativa do quicksort, parece que já tiveste a resposta.

gostava de sublinhar que um algoritmo iterativo nem sempre é mais eficiente do que o recursivo, pois caso precises de manter tu a stack, vais ter o mesmo problema que torna a versão recursiva lenta.

eu apenas digo que qualquer algoritmo recursivo pode ser transformado num iterativo.


[offtopic]

qual a diferença de tail-backtracking para backtracking "normal"?

[/offtopic]

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

oi oi oi oi... alguem não anda a trazer as lições bem estudadas, sem ofensa.

Warrior, clica no link que me deste e lê o que lá está escrito. Não quero dizer isto de forma ofensiva ou sarcástica: tudo me leva a crer que fizeste uma pesquisa no google de "quick sort non-recursive" e afixaste aquele link sem ler a página atentamente.

Rui carlos, lê tambem.

Penso que não preciso de acrescentar nada. Responde inclusive à questão da quantidade de código.

EDIT: ok... só para dar uma pista para a discussão nao se perder. Um algoritmo recursivo é iterativo, estão a confundir as coisas... n é iteratividade vs recursividade, n faz sentido isso. Se repararem na wikipedia dizem que é uma versao que nao usa recursividade explicita. Basicamente mudam a forma de guardar os dados que muda. A recursão continua implicita no algoritmo.

Já agora... o algoritmo é que é recursivo, n é o código.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

a recursividade está implícita como deve estar na maior parte da vezes que fazes um ciclo. por esse ponto de vista então quase tudo é recursivo...

o algoritmo é que é recursivo, mas tu falaste na implementação, eu por implementação entendo o código.

Por exemplo, implementa aí o quicksort numa linguagem qualquer sem usares recursividade... n consegues.

penso que já toda a gente sabe que o quicksort é um algoritmo recursivo, por isso a tua pergunta, se se referia ao facto do algoritmo ser recursivo ou não, não fazia qualquer sentido. o algoritmo é sempre o mesmo, logo ou é sempre recursivo ou nunca o é. a implementação é que pode variar, e se eu implemento a função quicksort sem a chamar dentro dela prórpia tenho um implementação não recursiva (independentemente do algoritmo ser recursivo ou não).

ou seja, no máximo podias dizer "implementa-me uma função que faça o mesmo que o quicksort que não use recursividade", dando liberdade para se escolher o algoritmo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Rui carlos, estás a contradizer-te...

ora le com atenção..

penso que já toda a gente sabe que o quicksort é um algoritmo recursivo, por isso a tua pergunta, se se referia ao facto do algoritmo ser recursivo ou não, não fazia qualquer sentido. o algoritmo é sempre o mesmo, logo ou é sempre recursivo ou nunca o é. a implementação é que pode variar, e se eu implemento a função quicksort sem a chamar dentro dela prórpia tenho um implementação não recursiva (independentemente do algoritmo ser recursivo ou não).

Uma implementação não recursiva de um algoritmo recursivo não existe. Chamo a atenção que a recursividade não é definida pela chamada de uma função dentro da propria função, de resto há linguagens que nem permitem isso.

Calculas um valor segundo um algoritmo, pegas nesse valor e submete-lo ao mesmo algoritmo, então aplicaste um algoritmo recursivo ao valor inicial.

Se reparares, a única função diferença nos dois códigos no link da wikipédia é a forma como são guardados os dados. Na primeira abordagem são guardados em variaveis com o mesmo nome em scopes diferentes, na segunda são postos todos numa pilha acessível globalmente.

Já viram a economia de código que se consegue?

a recursividade está implícita como deve estar na maior parte da vezes que fazes um ciclo. por esse ponto de vista então quase tudo é recursivo...

Não, ora pensa lá bem. Os ciclos podem ser utilizados para várias coisas: percorrer estruturas de dados, fazer escutas, em geral repetir procedimentos. Nem os próprios são implementados à cusa de uma solução recursiva. Basicamente um ciclo é um conjunto de saltos da posição do ponteiro de execulão, todos os dados são guardados noutros endereços de memória e nao vao utilizados para controlar o percurso da proxima iteração.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Rui carlos, estás a contradizer-te...

Uma implementação não recursiva de um algoritmo recursivo não existe. Chamo a atenção que a recursividade não é definida pela chamada de uma função dentro da propria função, de resto há linguagens que nem permitem isso.

Calculas um valor segundo um algoritmo, pegas nesse valor e submete-lo ao mesmo algoritmo, então aplicaste um algoritmo recursivo ao valor inicial.

é uma questão de ponto de vista!

como já referi anteriormente, se também estás a considerar a recursividade implícita, a tua questão não faria qualquer sentido.

Se reparares, a única função diferença nos dois códigos no link da wikipédia é a forma como são guardados os dados. Na primeira abordagem são guardados em variaveis com o mesmo nome em scopes diferentes, na segunda são postos todos numa pilha acessível globalmente.

Já viram a economia de código que se consegue?

alguma vez coloquei isso em causa?

acho que sempre disse que era isso que teria que ser feito...

a recursividade está implícita como deve estar na maior parte da vezes que fazes um ciclo. por esse ponto de vista então quase tudo é recursivo...

Não, ora pensa lá bem. Os ciclos podem ser utilizados para várias coisas: percorrer estruturas de dados, fazer escutas, em geral repetir procedimentos. Nem os próprios são implementados à cusa de uma solução recursiva. Basicamente um ciclo é um conjunto de saltos da posição do ponteiro de execulão, todos os dados são guardados noutros endereços de memória e nao vao utilizados para controlar o percurso da proxima iteração.

ou seja, os ciclos são usados para efectuar um conjunto de operações e voltar a repeti-las, algo que podes fazer de forma recursiva, aliás, linguagens como o haskell nem têm ciclos, logo qualquer algoritmo que noutra linguagem seja implementado com um ciclo, em Haskell é feito com recursividade, logo todos esses algoritmos podem ser considerados recursivos, não?

quando estamos a falar de recursividade implícita é complicado/subjectivo dizer quando é que existe ou não...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu acho, que não é nada dificil dizer quando há recursividade, já escrevi a definição neste tópico mais do que uma vez. Nem sequer interessa falarmos de linguagens para nada, é uma questão matemática.

Se essa linguagem não tem ciclos deve ter pelo menos saltos, ora pensa lá bem, não é na mesma imediato determinar se um algoritmo é recursivo ou não mesmo olhando para código nessa linguagem?

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