Recursividade

O assunto deste post será Recursividade e para prender a sua a atenção vou começar com uma piada clássica (dedicado a @lacerdaph):

Para entender a recursividade, antes, você tem que entender a recursividade.

 Agora vamos a parte técnica. Primeiro vou tentar definir de maneira simples, o que é recursividade:

Recursividade é a capacidade que uma função/método tem de invocar a si mesmo. 

Em outras palavras a recursividade é a maneira de dividir um problema em vários subproblemas sem adicionar nova complexidade.

Com isso em mente temos o seguinte exemplo:

public static void main(String[] args) {
 diminui(10);
}

private static void diminui(int i) {
 System.out.println(i);
 if (i > 0)
 diminui(i - 1);
}

O método "diminui" serve para imprimir uma sequencia de números de maneira decrescente até o número zero. Note que para isso não existe nenhuma estrutura de loop como "while" ou "for", apenas uma chamada a ele mesmo com um argumento menor que o inicial. Podemos dizer que o método diminui é recursivo por que ele faz uma chamado a si mesmo se o número ainda for maior que zero.

Podemos aplicar a recursividade em exemplos mais complexos como exibir uma estrutura de pastas e arquivos. Em java ficaria assim:

public static void main(String[] args) {
 listaConteudo(new File("/home/geraldo"));
}

private static void listaConteudo(File arquivo) {
 if (arquivo.isDirectory()) {

  System.out.println("Diretorio " + arquivo.getName());

  File[] subArquivos = arquivo.listFiles();
  for (File subArquivo : subArquivos) {
   listaConteudo(subArquivo);
  }

  } else {
   System.out.println(" Arquivo " + arquivo.getName());
  }
 }
}

Ou em exemplos mais didáticos como a sequência de Fibonacci:

public static void main(String[] args) {
 System.out.println(fibonacci(10));
}

public static int fibonacci(int n) {
 return n == 1 || n == 0 ? 1 : fibonacci(n - 1) + fibonacci(n - 2);
}

Algo pra se ter em mente é que todo algoritmo recursivo pode ser feito também de maneira interativa. Em termos de performance é quase sempre mais vantajoso usar o algoritmo interativo, isso porque as linguagens que permitem execuções recursivas trabalham usando uma pilha de chamada ou um stack de execução.

Podemos entender a pilha como sendo o local onde a linguagem guarda o estado de cada método sendo executado. O último método na pilha é o que está sendo executado no momento como mostra a imagem a seguir:

Com isso podemos verificar que a maior limitação de uma chamada de método recursivo é o tamanho da pilha. Isso quer dizer que  se chegarmos a capacidade máxima da pilha não conseguiremos fazer chamada de nenhum outro método provocando um estouro na pilha (StackOverflow).

Existem alguns tipos de chamada recursiva e a escolha da mesma pode melhorar/otimizar o uso da pilha permitindo mais empilhamento de métodoos.

Recursividade simples: é quando fazemos apenas uma chamada recursiva por vez. Ex: o método diminui.
Recursividade dupla: é quando fazemos 2 ou mais chamadas recursivas por vez. Ex: o método fibonacci.
Recursividade em Cauda: é quando a chamada recursiva é a última instrução executada.

Vou focar nesta última pois acho que é a que traz o ganho mais significativo.
Para se trabalhar com a recursão em cauda, não basta ser a última linha de código, tem que ser a ultima instrução a ser executada pelo processador. No exemplo abaixo vamos calcular o fatorial de um número, parece que estamos usando recursão em cauda, mas note que a ultima instrução executada será a multiplicação de "n" e o retorno da chamada recursiva:

public static long fatorial(long n) {
 if (n == 0) return 1;
  return n * fatorial(n - 1);
 }
}

Isso faz com que a linguagem tenha que manter o método na pilha pra poder executar a multiplicação. No exemplo abaixo, visto que não tem mais nada pra fazer quando voltar da chamada recursiva, não é necessário manter esse método na pilha, então a linguagem pode remove-lo abrindo espaço para outra chamada.

public static long fatorial(long n, long acumulador) {
 if (n == 0) 
  return acumulador;
 return fatorial(n - 1, n * acumulador);
}

public static long factorial(long n) {
 return fatorial(n, 1);
}

Uma outra forma de ganhar performance e otimizar o uso da pilha é aplicar uma técnica chamada Memoization que consiste em guardar algum valor previamente calculado evitando assim um novo empilhamento e evitando o custo de processamento. Veja no exemplo abaixo novamente o cálculo da sequencia de Fibonacci:

private static Map<Long, Long> jaCalculados = new HashMap<Long, Long>();

public static long fibonacciMemoization(long n) {
 if (jaCalculados.containsKey(n))
  return jaCalculados.get(n);

 Long valorCalculado;
 if (n == 0 || n == 1)
  valorCalculado = n;
 else
  valorCalculado = fibonacciMemoization( n - 1 )+ fibonacciMemoization(n - 2);

 jaCalculados.put(new Long(n), valorCalculado);
 
 return valorCalculado;

}

Após muita conversa com amigos (@moreira_caelum e @renatoargh)  cheguei a conclusão de que gosto de recursividade quando a implementação torna o código mais expressivo e legível sem impactar significativamente no desempenho. A partir do momento em que a recursividade prejudica o entendimento ou a performance do algoritmo, prefiro o modelo iterativo.


Referências:
Recursividade (Wikipedia)
Recursividade Simples, Dupla e em Cauda
Recursividade em cauda
Memoization (Wikipedia)
Dica de leitura Analise de Algoritmo