Recursividade

  Estava assistindo uma aula de Scala e em um dos exercícios tinhamos que implementar um método para descobrir a soma de uma lista de inteiros, porém o exercicio dava a sugestão de usar recursividade ao invés de fazer um loop.

  Neste post vou mostrar o raciocinio que utilizei para resolver o exercicio e mostrar como eles seriam resolvidos passo a passo em Java.

  Mas antes um pouco de teoria:

• Para entender recursividade, você precisa entender recursividade.
• PHP é um acronimo recursivo que significa: PHP: Hypertext Processor
• WINE é outro exemplo de recursividade, a sigla significa: Wine Is Not an Emulator
• outro exemplo é GNU que significa: Gnu's Not Unix

Deu pra ver onde quero chegar? em todos os casos acima você acaba criando um laço de repetição, pra entender recursividade, você tem que entender recursividade, então vá entender recursividade, pra isso você tem que entender recursividade... Ok parei.
Parece complicado, mas  na verdade é simples. Recursividade nada mais é do que chamar o metodo que está sendo declarado dentro de seu próprio corpo. Como exemplo, temos um metodo para ver o N numero da sequencia de Fibonacci:

    public static long fibonacci (int i) {
        if (i == 1) return 0;
        if (i == 2) return 1;

        long numero = fibonacci(i - 1) + fibonacci(i - 2);
        return numero;
    }

Olhos atentos perceberam que o metodo fibonacci, chama o metodo fibonacci logo antes de dar o return, isso é chamado de metodo recursivo.
  O que ocorre ali é o seguinte: A sequencia de fibonacci define que

• primeiro termo da sequencia é 0
• o segundo termo da sequencia é 1
• a partir daí, o termo n é igual ao termo n-1 somado do termo n-2

Viu como é simples enxergar estas regras no codigo acima? Na hora que o metodo fosse executado com o argumento 5, ele se expandiria, e aconteceria algo +- assim:
fibonacci(5) = fibonacci(4) + fibonacci(3)

sabemos que fibonacci de 4 é igual a fibonacci de 3 + fibonacci de 2 então:

fibonacci(5) = fibonacci(3) + fibonacci(2) + fibonacci(3)

sabemos que fibonacci de 3 é igual a fibonacci de 2 + fibonacci de 1 se substituirmos isso na nossa igualdade temos:

fibonacci(5) = fibonacci(2) + fibonacci(1) + fibonacci(2) + fibonacci(2) + fibonacci(1)

pela definição da sequencia de fibonacci, sabemos que fibonacci(2) = 1 e fibonacci(1) = 0. subsitituindo isto na igualdade temos:

fibonacci(5) = 1 + 0 + 1 + 1 + 0
fibonacci(5) = 3

Pronto. Recursivamente descobrimos que o quinto termo da sequencia de fibonacci é 3, o que bate com a sequencia mostrada na wikipedia (linkada ali em cima)

Agora vamos implementar o método para descobrir a soma da lista.

Se fossemos utilizar a solução com o loop, seria mais ou menos assim:

    public static int somaLista(ArrayList<Integer> lista){
        int total=0;
        for (int i=0; i < lista.size(); i++){
            total = total + lista.get(i);
        }
        return total;
    }

Agora vamos pensar recursivamente:
primeiro precisamos definir uma regra para nos tirar do loop, assim, alguma hora vamos parar de invocar o método. Queremos somar os elementos da lista, então, se a lista estiver vazia, a soma será 0. Logo nossa regra é:

• Se a lista estiver vazia, o resultado da soma é zero

Para que nossa regra nos ajude, a lista deverá diminuir a cada chamada do método, assim uma hora ela ficará vazia e terminaremos nossa execução. Então na hora de implementar o código vamos remover o primeiro elemento da lista, e somar com o resto da lista. O código fica assim:

    public static int somaListaRecursivo(List<Integer> lista){
                
        if (lista.isEmpty()) return 0;
        
        int aux=lista.get(0);
        lista.remove(0);
        
        return aux + somaListaRecursivo(lista);
    }

Ao executarmos o código

    public static void main(String[] args) {
        ArrayList<Integer> l = new ArrayList<>();
        l.add(2);
        l.add(3);
        l.add(3);
        System.out.println(somaListaRecursivo(l));
    }

temos a saida 8.

Como sempre, se tiver alguma dúvida, sugestão ou critica, deixe nos comentarios.