Olá.
Alguém poderia por favor me explicar recursividade ?
Já tenho uma noção sobre ela, mas quero entender melhor.
Obrigada.
Abraço
é uma função que chama a sí mesma pra resolver determinado problema…
fiz um exemplo veja:
[code]
public class recusivo {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(fatorial(5));
}
private static int fatorial(int n){
if(n==1)
return n;
return fatorial(n-1)*n;
}
}[/code]
sabemos que o fatorial de 5 é 54!, o fatorial de 4 é 43!..
então o que acontece… a função vai chamar a si própria até chegar em 1 que é a condição de parada.
funciona como se fosse loop na primeira rodada o n vale 5 então ela vai chamar a si própria passando o próximo valor de n (n-1) para ela msm e o valor do n atual (n)
que equivale a 5*(4!) e assim sucessivamente até n==1 .
humm… entendi. brigada
então posso considerar ela como uma laço de repetição que trabalha por si própria e vai se resolvendo até chegar num critério de parada?
sim… seria uma função ou método(nesse caso) que funciona de forma parecida com uma estrutura de repetição, pois tem a habilidade de chamar a si própria para resolver determinado problema.
Aproveitando o topico, a recursividade não é mais ‘custosa’?
Tenho uma classe que tambem preciso calcular o fatorial, só que faço com ‘for’, não vi motivos para usar recursividade.
Analise combinatória com tamanhos variaveis, tambem vejo que todos usam recursividade, porem creio que possa ser feito sem tambem.
Minha analise tá errada?
Não tá errada não.
Assim para problemas pequenos você não tem necessidade de usar a recursividade.
Ela se adequa mais para problemas grandes em que uma operação se repita mais de uma vez.
Fica mais fácil você criar um método recursivo e chamar ele quando necessário do que ter de digitar todo o código outra vez.
Você acaba ganhando tempo e precisão no código.
[quote=asousaj]Aproveitando o topico, a recursividade não é mais ‘custosa’?
Tenho uma classe que tambem preciso calcular o fatorial, só que faço com ‘for’, não vi motivos para usar recursividade.
Analise combinatória com tamanhos variaveis, tambem vejo que todos usam recursividade, porem creio que possa ser feito sem tambem.
Minha analise tá errada?[/quote]
como a Geisebel disse nesse caso recursividade não é a forma mas adequada, pois ela usa mais memoria seria melhor usar um loop normal.
em java acho que não tem muita vantagem de se usar recursividade, já que a linguagem não permite gerenciamento de memoria como em C, a recursividade é
mais adequada para estrutura de dados lista encadeada, arvore, paginação de arvore…
nao é adequada para problemas que tem a resoluçao obvia por interação(fatorial,fibonaci,soma de termos).
Em que tipo de programas vocês já usaram recursividade?
To aprendendo agora.
Nunca usei ela em programação só fiz testes de mesa recursivos.
Puxa, alivio … tava pensando q eu era um aliem, diferente dos outros.
Pesquise analise combinatória em java na web, verá que todos usam recursividade, vai ver é pq copiaram o algoritmo do ‘C’.
Grato pelo retorno.
Para fatorial tbm…
até meus professores todos usam esse exemplo de recursividade.
[quote=geisebel]Em que tipo de programas vocês já usaram recursividade?
To aprendendo agora.
Nunca usei ela em programação só fiz testes de mesa recursivos.[/quote]
é mais usado em estruturas que tem a natureza recursiva lista encadeada,lista duplamente encadeada, arvore…estrutura de dados.
eu posso tá enganado mas eles fazem o fatorial recursivo pq é mais fácil de entender nao pq é mais eficiente…
seria mais difícil de explicar recursividade usando uma lista encadeada do que usando fatorial.
o fatorial recursivo usa mais memoria e tem uma complexidade maior que seria O(n)! enquanto o fatorial nao recursivo tem complexidade O(1).
a minha opinião é que o ideal é só recursão quando for “necessário”, por quê além de ser mais custoso é menos intuitivo também, menos fácil de entender do que um loop caso este possa fazer a mesma coisa. Como exemplo disso teríamos o padrão decorator. Ja tive problemas onde precisei armazenar itens na base organizados como árvores e processar os itens onde o processamento de um item depende do processamento do item abaixo dele, esse é outro bom exemplo.
Como disseram aí acima, recursão deve ser usado com cautela. se vc resolve o problema com um laço simples, use o laço. A recursão faz muito uso do Heap e, dependendo do tamanho do problema, a possibilidade de estourar a pilha de execução é imensa.
Entretanto, para problemas intrisicamente recursivos, aí não tem como fugir. Por exemplo, resolver o problema da torre de hanói sem recursão é beeem complicado. Ou mesmo resolver funções do tipo:
T(n) = T(n-1) + 3T(n-2) + 1;Falando de problemas reais (não exercicios para o entendimento do funcionamento) recursividade e loops tem objetivos totalmente diferentes…
O loop (for, while, etc) tem por objetivo percorrer alguma estrutura de dados (lista, pilha fila, etc…).
Recursividade significa um metodo por exemplo chamar ele mesmo a fim de resolver algo.
Ja que citaram exemplos de faculdade…o metodo de ordenação QuickSort utiliza de recursividade e não tem como vc implementar ele usando um loop qualquer.
Recursividade não é um loop. Os exemplos que utilizam para demostrar a recursividade que acabam deixando esta ideia.
Digamos que vc tem um loop e no meio do bloco do seu loop vc queira executar todo este mesmo bloco novamente e depois continuar do mesmo ponto onde parou para executar o bloco completo:
for(.......){
//começo do meu codigo
//vamos imaginar que aqui eu tenho que executar tudo que esta dentro desde bloco
//e depois continuar deste ponto
//fim do meu codigo
}
Não tem outra forma de eu fazer isso sem ser com recursividade.
Isso nãio teria que ser um loop e sim um metodo que ira ser chamado n vezes dependendo da necessidade
Otima explicação Lucas.
Realmente pesquisei e melhor usar recursividade onde a logica(formula) seja recursiva.
Abç!