Bom,
Comecei a ver alguns exemplos de recursividade ( Fibonnacci, Fatorial etc … )
e gostaria de uma ajuda com uma dúvida que tive …
é possível preencher um vetor usando recursividade ?
alguém pode me dar um exemplo ? rascunhei algumas
tentativas aqui e não me vem nada a cabeça …
Alguma sugestão de bons exercícios para trabalhar com
recursão ??
Perfeitamente possível. Pensei em algo bastante simples, dá uma olhada e veja se entende
public class RecursaoVetor {
/**
Exemplo que preenche um vetor com os valores
iguais a cada indice.
*/
private static void preencheVetor(int[] vetor, int pos) {
if(pos == vetor.length - 1) return;
vetor[pos] = pos;
preencheVetor(vetor, pos + 1);
}
public static void main(String args[]) {
int[] vetor = new int[10];
preencheVetor(vetor, 0);
for(int i = 0; i < vetor.length; ++i) System.out.print(i + " ");
}
}entendi.
eu posso falar que um método recursivo funciona como uma laço ?
Que consome mais memória …
tô apanhando um pouco pra pensar recursivamente … !
Funciona de forma parecida a um laço, se você pensar no aspecto repetitivo de uma chamada recursiva. Repetitivo pois uma função (ou método) recursivo chama a si mesma n vezes, até que uma dada condição seja satisfeita e a função (ou método) retorne.
O consumo de memória realmente é um pouco maior, pois as chamadas são empilhadas e liberadas da memória somente quando a condição trivial (quando a função pára de chamar a si mesma) é alcançada e todas as chamadas retornam.
Outra forma de preencher o vetor usando recursividade.
A idéia é a seguinte:
class PreencherVetorRecursivo {
/**
* @param vec O vetor a ser preenchido
* @param start A posição inicial a ser preenchida
* @param end A posição final a ser preenchida MAIS UM (como o método String.substring)
* @param val O valor que deve ser usado para preencher o vetor.
*/
public static void preencher (int[] vec, int start, int end, int val) {
if (start >= end) return; // 0 elementos, ou então chamada inválida
if (start + 1 == end) { // ou seja, só um elemento
vec[start] = val;
} else {
// Preencher a primeira metade
preencher (vec, start, (start + end) / 2, val);
// Preencher a segunda metade
preencher (vec, (start + end) / 2, end, val);
}
}
public static void main(String[] args) {
int[] valores = new int[1234];
final int THE_ANSWER = 42;
// Efetuando o preenchimento recursivo...
preencher (valores, 0, valores.length, THE_ANSWER);
// Aqui estamos checando para ver se todos os valores são realmente 42
// - não se esqueça que em Java, ao alocar um vetor os valores são 0 ou null.
boolean ok = true;
for (int i = 0; i < valores.length; ++i) {
if (valores [i] != THE_ANSWER) {
ok = false;
break;
}
}
if (!ok) {
System.out.println ("Não conseguiu preencher o vetor adequadamente");
} else {
System.out.println ("O vetor foi adequadamente preenchido.");
}
}
}Estou dando esse exemplo de “quebrar o vetor no meio” porque ele se parece um pouco com o quicksort, que também funciona de forma parecida.
Muitos problemas recursivos se resolvem quebrando o problema em pedaços, até que o problema seja suficientemente pequeno para ser resolvido de maneira simples.
No exemplo que lhe passei, eu quebrei o problema em 2, e cada subproblema em 2, até que o problema fosse bem pequeninho (preencher apenas 1 posição do vetor).
Pra você ter noção do quanto um algoritmo recursivo consome mais memória que um não-recursivo, e já que vc quer um exercício, faça algo assim, pra brincar e testar:
Cria aí uma classe que exiba na tela os elementos 1, 2, 3 … 10, 15, 20, 25, 30, 40 de uma Fibonacci. Só que nesse seu programa, crie dois métodos distintos para buscar o n-ésimo elemento da série de Fibonacci, um recursivo e outro não recursivo. No main da sua classe, faça o programa então exibir algo assim na tela:
Utilizando algoritmo NÃO-recursivo:
Elemento 1 = 1
Elemento 2 = 1
Elemento 3 = 2
Elemento 4 = 3
Elemento 5 = 5
Elemento 6 = 8
Elemento 7 = 13
Elemento 8 = 21
Elemento 9 = 34
Elemento 10 = 55
Elemento 15 = 610
Elemento 20 = 6765
Elemento 25 = 75025
Elemento 30 = 832040
Elemento 35 = 9227465
Elemento 40 = 102334155
=======================
Utilizando algoritmo recursivo:
...Divirta-se!
Existem maneiras e maneiras de fazer a recursividade. Nem sempre a recursividade usa assim mais memória.
O jeito que o Cassio lhe passou “explode” em Java quando o número de elementos do vetor é por volta de 90.000; o meu jeito (quebrando o problema sempre em “metades”) “explode” bem mais devagar. Na prática, meu jeito não deve explodir a pilha (stack) do Java - isso porque o maior tamanho de um vetor em Java são 2^31 elementos e com esse valor uso apenas 32 níveis de recursão, em vez de 2^31 níveis de recursão.
Nem sempre métodos recursivos são tão lentos quanto se pensa. É questão de saber algumas técnicas.
A que vou mostrar agora é a tal de “memoizing”. Rode este programa e você vai ver que Fibonacci não é tão lento assim recursivamente.
import java.util.*;
/**
* "Memoizing" (que eu vou traduzir por "memorização") é uma técnica de acelerar programas
* recursivos guardando resultados já calculados.
* Embora existam maneiras mais simples e eficientes de calcular os números de Fibonacci, vou
* mostrar uma técnica genérica que não exige mexer muito no seu algoritmo.
* Como vocês devem saber:
* fibonacci (0) = 0
* fibonacci (1) = 1
* fibonacci (n) = fibonacci (n - 1) + fibonacci (n - 2)
*/
class FibonacciComMemorizacao {
Map<Integer,Integer> preCalculado = new TreeMap<Integer,Integer>();
public FibonacciComMemorizacao() {
preCalculado.put (0, 0); // fibonacci (0) = 0
preCalculado.put (1, 1); // fibonacci (1) = 1
}
public int fibonacci (int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else if (n > 1) { // fibonacci (n) = fibonacci (n - 1) + fibonacci (n - 2)
Integer f = preCalculado.get (n); // vamos ver se já foi calculado antes...
if (f != null) {
// volto o valor pré-calculado!
return f;
} else {
// Não tem jeito, tem de calcular pela fórmula recursiva
f = fibonacci (n - 1) + fibonacci (n - 2);
// E agora vamos guardar o resultado
preCalculado.put (n, f);
return f;
}
} else {
throw new IllegalArgumentException ("Definido apenas para os números positivos.");
}
}
public static void main(String[] args) {
FibonacciComMemorizacao fcm = new FibonacciComMemorizacao();
Integer[] valores = {
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 20, 25, 30, 35, 40
};
/*
Valores esperados: (veja a seqüência http://www.research.att.com/~njas/sequences/A000045)
Fibonacci (1) = 1
Fibonacci (2) = 1
Fibonacci (3) = 2
Fibonacci (4) = 3
Fibonacci (5) = 5
Fibonacci (6) = 8
Fibonacci (7) = 13
Fibonacci (8) = 21
Fibonacci (9) = 34
Fibonacci (10) = 55
Fibonacci (15) = 610
Fibonacci (20) = 6765
Fibonacci (25) = 75025
Fibonacci (30) = 832040
Fibonacci (35) = 9227465
Fibonacci (40) = 102334155
*/
for (int i = 0; i < valores.length; ++i) {
System.out.println ("Fibonacci (" + valores[i] + ") = " + fcm.fibonacci (valores[i]));
}
}
}Eu usei, no “memoizing”, um Map<Integer,Integer> em vez de um int[] (como você também poderia fazer) para exemplificar uma técnica genérica.
É que nem sempre os valores recursivos são assim tão contíguos, como é o caso do Fibonacci.
Sugestão: modifiquem meu programa para usar BigInteger em vez de long. Se você calcular fibonacci (10000), vai ver que o valor é:
Fibonacci (10000) = 336447648764317832666216120051075433103021484606800639065647
69974680081442166662368155595513633734025582065332680836159373734790483865268263
04089246305643188735454436955982749160660209988418393386465273130008883026923567
36131351175792974378544137521305205043477016022647583189065278908551543661595829
87279682987510631200575428783453215515103870818298969791613127856265033195487140
21428753269818796204693609787990035096230229102636813149319527563022783762844154
03605844025721143349611800230912082870460889239623288354615057765832712525460935
91128203925285393434620904245248929403901706233888991085841065183173360437470737
90855263176432573399371287193758774689747992630583706574283016163740896917842637
86242128352581128205163702980893320999057079200643674262023897831114700540749984
59250360633560933883831923386783056136435351892133279732908133732642652633989763
92272340788292817795358057099369104917547080893184105614632233821746563732124822
63830921032977016480547262438423748624114530938122065649140327510866433945175121
61526545361333111314042436854805106765843493523836959653428071768775328348234345
55736671973139274627362910821067928078471803532913117677892465908993863545932789
45237776744061922403376386740040213303432974969020283281459334188268176838930720
03634795623117103101291953169794607632737589253530772552375943788434504067715555
77905645044301664011946258097221672975861502696844314695203461493229110597067624
32685159928347098912847067408620085871350162603120719031720860940812983215810772
82076353186624611278245537208532365305775956430072517744315051539600905168603220
34916322264088524885243315805153484962243484829938090507048348244932745373262456
77558790891871908036620580095947431500524025327097469953187707243768259074199396
32265984147498193609285223945039707165443156421328157688908058783183404917434556
27052022356484649519611246026831397097506938264870661326450766507461151267752274
86215986425307112984411826226610571635150692600298617049454250474913781151541399
41550671256271197133252763631939606902895650288268608362241082050562430701794976
171121233066073310059947366875Grato a todos pela ajuda !
vou continuar praticando aqui até melhorar !
dei uma olhada no algoritmo do QuickSort e nao gostei muito da cara dele !
:shock:
Para praticar com algo prático mesmo (que você vai sempre usar), tente listar os subdiretórios de um diretório, recursivamente.
Acho que há alguns exemplos desse aqui no fórum; encontre-os e veja como foram feitos.
Thingol,
Existe algum forma de fazer a pratica que vc sugere de uma forma mais elegante como por exemplo a tecnica de divisão, já que eu acredito que a de memorização não vai rolar para este caso.
Fazendo na força bruta, da forma que o cassio indicou eu fiz numa boa, so que com mais elegancia eu não consegui, pois não tive nenhuma boa idéia de algoritmo.Sr (ou sra.) Ovelha (eu desliguei todas as figuras do GUJ, até por uma questão de equanimidade e não consigo ver seu avatar):
Qual é o seu problema? Em recursão não existem “melhores práticas”; e há diferentes maneiras de fazer a mesma coisa.