Uso de Recursividade

Programação Java
#1

Existe alguma vantagem em se usar algoritmo recursivo em Java? O que a recursividade afeta no desempenho da aplicação?

Obrigado.

#2

Java não é uma linguagem muito 'otimizada" para algoritmos recursivos se você precisar dos seguintes recursos que linguagens orientadas para algoritmos recursivos normalmente têm:

a) “Tail-call optimization” - em determinadas condições, um algoritmo recursivo é automaticamente transformado em um iterativo pelo runtime da linguagem, e isso economiza espaço em pilha.

b) Pilha de execução alocada dinamicamente (no Java essa pilha tem tamanho fixo, dada pelo parâmetro da JVM “-Xss” ).

#3

Basicamente, chamadas de métodos adicionam um overhead no processamento, em função de empilhar variáveis locais e registradores. Mas na maioria das vezes, o inimigo em algoritmos recursivos não é esse overhead, e sim o próprio algoritmo, que pode gerar recalculos e aumentar a complexidade desnecessariamente. O exemplo clássico é a série de fibonnaci, que na sua versão recursiva é muito mais cara do que a versão iterativa. Por outro lado,em algoritmos como quicksort, busca em árvore binária, etc. a diferença deve ser muito pouca.

#4

Uma das vantagens é que alguns algorítmos (especialmente os de árvore) ficam muito mais claros de maneira recursiva.

#5

Diga como é que você lista os arquivos em diretórios e subdiretórios, ou os registros de uma JTree, sem usar um algoritmo recursivo.
Isso é possível usando pilhas, mas o algoritmo torna-se difícil de entender se não for em forma recursiva.

Um exemplo de como é possível listar recursivamente os arquivos em diretórios e subdiretórios (veja o método “listarArquivos” abaixo). Ele é muito simples de entender e é recursivo.

Como normalmente não há 10000 níveis de diretórios em um sistema de arquivos, mas sim muito menos, o método recursivo não irá explodir a pilha de execução do Java.

import java.util.*;
import java.util.concurrent.*;
import java.io.*;
import java.security.*;
import java.nio.*;
import java.nio.channels.*;
import java.math.*;

class AcharArquivosIguais {
    public AcharArquivosIguais() {
    }
    public void listarArquivos (File diretorio, Set<File> arquivos) {
        File[] listagem = diretorio.listFiles();
        for (File f : listagem) {
            if (f.isDirectory() && !f.getName().equals (".") && !f.getName().equals ("..")) {
                listarArquivos (f, arquivos);
            } else {
                arquivos.add (f);
            }
        }
    }
    private static byte[] buffer = new byte[10 * 1024 * 1024];
    private static String hashFile (File arq) {
        String s = "error";
        try {
/*		
            MessageDigest dgst = MessageDigest.getInstance ("SHA1");
            FileInputStream fis = new FileInputStream (arq); 
            int nBytes;
            dgst.reset();
            while ((nBytes = fis.read (buffer)) > 0) {
                 dgst.update (buffer, 0, nBytes);
            }
            byte[] bytes = dgst.digest();
            fis.close();
*/
            MessageDigest dgst = MessageDigest.getInstance ("SHA1");
			DigestInputStream dis = new DigestInputStream (new FileInputStream (arq), dgst);
            int nBytes;
            dgst.reset();
            while ((nBytes = dis.read (buffer)) > 0) {
            }
			dis.close();
            byte[] bytes = dgst.digest();
            BigInteger bd = new BigInteger (bytes);
            s = bd.toString (16);
        } catch (NoSuchAlgorithmException ex) {
        } catch (IOException ex) {
            ex.printStackTrace();
        }
        return s;
    }
    public void acharArquivosIguais (Collection<File> arquivos) {
		Map<String, List<File>> hash2file = new ConcurrentHashMap<String, List<File>>();
		int n = 1;
        for (File f : arquivos) {
            System.err.printf ("\r%7d %,8dK %-61.61s", n, f.length() / 1024, f.getName());
			
            String hash = hashFile (f);
            List<File> files;
            if (!hash2file.containsKey (hash)) {
                files = new ArrayList<File>();
                hash2file.put (hash, files);
            } else {
                files = hash2file.get (hash);
            }
            files.add (f);
			++n;
        }
        System.out.println ();
        // Agora vamos ver, nessa lista, que arquivos têm mais de uma entrada.
        boolean arquivosRepetidos = false;
        for (Map.Entry<String, List<File>> h2f : hash2file.entrySet()) {
            if (h2f.getValue().size() > 1) {
                arquivosRepetidos = true;
                System.out.println ("---");
                System.out.println (h2f.getValue().size() + " arquivos com o hash " + h2f.getKey() + ":");
                System.out.println ("---");
                for (File f : h2f.getValue()) {
                    System.out.println ("    " + f);
                }
            }
        }
        if (!arquivosRepetidos) {
            System.out.println ("Não foram encontrados arquivos repetidos.");
        }
    }

    public static void main(String[] args) {
        if (args.length != 1) {
            System.err.println ("Sintaxe: java -cp . AcharArquivosIguais diretorio");
            System.exit (1);
        }
        AcharArquivosIguais aai = new AcharArquivosIguais();
        Set<File> arquivos = new TreeSet<File>(new Comparator<File>() {
		    public int compare(File o1, File o2) {
			    String n1 = o1.getName();
				String n2 = o2.getName();
				int cmp = n1.compareToIgnoreCase (n2);
				if (cmp == 0) return o1.compareTo (o2);
				else return cmp;
			}
		});
        System.err.println ("Procurando os arquivos...");
        aai.listarArquivos (new File (args[0]), arquivos);
        System.err.printf ("Lendo os %d arquivos...%n", arquivos.size());
        aai.acharArquivosIguais (arquivos);
    }
}
#6