Recursão ou método recursivo nada mais é do que um método que, em sua implementação, chama a si mesmo.

Mas você deve estar se perguntando para que isso me serve? Bom tecnicamente você pode fazer com iteração tudo o que você pode fazer com recursão, mas para alguns problemas computacionais as soluções recursivas tornam-se mais simples. Em geral quando você pode simplificar um problema, sem deixar de ser o mesmo problema, até que ele se torne menor e de mais fácil resolução é um problema que pode ser resolvido com recursão.

Um exemplo clássico de Recursão é a Seqüência de Fibonacci que é uma seqüência que se obtém somando os dois últimos números da seqüência para chegar ao próximo. Vejamos uma implementação recursiva do problema onde mostramos na tela o 6º elemento da seqüência. 

class Fibonacci{
 
    public static int fiboRecursivo(int n){
        if( n <= 2){
            return 1;
        }else{
            return Fibonacci.fiboRecursivo(n - 1) + Fibonacci.fiboRecursivo(n - 2);
        }
    }
 
    public static void main(String args[]){
        int i = Fibonacci.fiboRecursivo(6);
        System.out.println(i);
    }
 
}

O problema da seqüência de Fibonacci pode ser resolvido pela fórmula F(n-1)+F(n-2) sendo que n é posição do elemento dentro da seqüência. Como sabemos o primeiro e o segundo elementos da seqüência são 1 chegamos a seguinte simplificação do problema.

  • SE a posição for menor ou igual a 2 retornamos 1
  • SENÃO simplificamos o problema, tentamos descobrir os dois elementos anteriores ao elemento que queremos, fazemos isso chamando o método fiboRecursivo e somamos suas saídas.

Ok, o código fica simples, mas e ai? Como ele é executado?

Toda chamada de um método é empilhada em um estrutura de pilha (memória Stack) que isola a área de memória de cada método. Quando fazemos uma chamada a um método a seqüência de execução é parada e passa a executar as instruções que o método chamado contem. O método chamado é empilhado na memória Stack(pilha) e após sua execução é retirado da memória Stack e seqüência de execução volta ao método que o chamou e a execução prossegue normalmente. Note que o método que está sendo executado sempre estará no topo da memória Stack.

Quando utilizamos chamadas recursivas estamos colocando métodos na memória Stack, para cada chamada ao método fiboRecursivo() uma “cópia” dele é colocada na memória e só será retirada quando as chamadas do topo da pilha parar de chamar o métodos e retornar algum valor.

Essa “cópia” é totalmente independente das outras, tem seu próprio escopo, variáveis locais e como qualquer método podem manipular atributos.

chamada_metodos

Um outro exemplo(mais prático) em que podemos utilizar a recursão é para listar os arquivos de um diretório e de seus subdiretórios como no exemplo abaixo.

import java.io.File;
import java.util.ArrayList;
import java.util.Iterator;
 
 
public class Diretorios {
 
    private ArrayList<File> arquivos = new ArrayList<File>();
 
    public void leDiretorio(File dir){
        File[] names = dir.listFiles();
        if( names != null){
            for(int i=0 ; i <names.length;i++){
                if( !names[i].isDirectory() ){
                    this.arquivos.add(names[i]);
                }else{
                    leDiretorio(names[i] );
                }
 
            }
        }
    }
 
    public static void main(String args[]){
        Diretorios d = new Diretorios();
        File f= new File("teste");
        d.leDiretorio(f);
 
 
        Iterator i = d.arquivos.iterator();
        while(i.hasNext()){
            System.out.println( i.next() );
        }
 
    }
}

O código do método leDiretorio faz o seguinte, ele recebe por parâmetro um File que deve ser um diretório, após isso ele lê todos os arquivos do diretório com o método listFiles(), após isso ele verifica se foi retornado algum arquivo(File), se sim ele percorre esse array testando se o arquivo não é um diretório ele armazena em um ArrayList se for ele faz chama uma chamada ao próprio método passando por parâmetro esse diretório.

Recursão é uma ferramenta bastante poderosa que pode simplificar muita coisa, embora tenha um custo computacional um pouco mais elevado permite a criação de códigos mais simples e por conseqüência de mais fácil manutenção.

Uma dica é que recursão é uma boa saída para percorrer qualquer estrutura no formato de árvore.