?Recursividade

Cara, recursividade é realmente complicado para pegar o jeito… Mas depois que vc pega o jeito, se torna usual.

Entenda recursividade como algo definido por ele mesmo. O exemplo mais usado em cursos de estrutura de dados é do fatorial. Como se calcula o fatorial de 5, por exemplo? Não seria:

fatorial(5) = 54321

e isso não seria a mesma coisa que dizer:

fatorial(5)= 5*fatorial(4)

e o fatorial de 4:
fatorial(4)= 4*fatorial(3)

e assim sucessivamente, até chegar no número 1, que dá um mesmo.

Acabamos de mostrar matematicamente o uso de recursividade. Agora você sabe que o fatorial de 5 é ele mesmo vezes o fatorial dele menos um. Então, como colocar isso em Java, por exemplo?

public class Fatorial
{
    
      public int calcula(int num)
     {
           // esse é o critério de parada. Sem essa condição, as chamadas
          //  recursivas à função ficam infinitas, ou seja, dá pau
           if ((num == 1) || (num == 0))
                  return 1;
           else
                  // lembra que acabamos de fazer isso ali em cima?
                  return num * calcula(num-1); 
     }
}

Bem, esse foi um exemplo simples, mas a recursividade é um recurso muito usado em muitas áreas, como algoritmos de busca, árvores, ordenação, etc.

Bom estudo!

bragil

Outra coisa, todo algoritmo recursivo pode ser implementado através de laços (while, for, do … while, etc). A diferença é que através da recursividade o código fica muito mais limpo. O que você gasta 2 ou 3 linhas para fazer com recursividade, pode-se gastar 10 ou 15 linhas usando laços.

Além disso, algoritmos recursivos gastam mais memória, pelo fato das sucessivas chamadas a função/método. Dependendo do ambiente do programa é bom evitar recursividade, como em dispositivos com limitações de hardware (dispositivos embarcados, PDAs, etc.).

Falow!

bragil

o fatorial eh o ex mais usado qnto a recursividade, mas um simples for jah daria um jeito:

public int fatorial(int num){
 if (fatorial < 0) throw new RuntimeException("O numero deve ser natural.");
 int total = num;
 for (int i = num; i > 1; i--) total *= i;
 return total;
}

um ex que eu acho mais apropriado, seria listar todos os arquivos do computador, pois ai sim, sem usar recursividade vai ficar MUITO complicado (isso se nao for impossivel)…

public class Teste{
 private ArrayList arquivos;
 public static void main(String args[]){
  arquivos = new ArrayList();
  File roots[] = File.listRoots();
  for (int i = 0; i < roots.length; i++) lista(roots[i]);
 }
 public static void lista(File f){
  File l[] = f.listFiles();
  for (int i = 0; i < l.length; i++){
   if (l[i].isFile()) arquivos.add(l[i]);
   else lista(l[i]);
  }
 }
}

nesse ex, comeca com as raizes (em Linux “/” e em windows “A:”, “C:”, “D:”…) e vai listando os arquivos, se for uma subpasta, ela eh passada recursivamente para ler listada tambem…

outro exemplo onde a recursividade eh importante eh no algoritimo do quicksort…