Java Recursão

Um método pode chamar qualquer outro método, inclusive ele mesmo. Quando isso acontece, dizemos que o método é recursivo. A recursão resolve um problema grande quebrando-o em uma versão menor do mesmo problema, até chegar a um caso tão pequeno que a resposta é óbvia.

Esta aula usa tudo das anteriores: métodos, parâmetros, retorno e if. Se algum deles ainda está nebuloso, revise antes.

A ideia antes do código: a fila do cinema

A Ana está numa fila escura de cinema e quer saber em que posição está. Ela não consegue contar as pessoas. Então pergunta para a pessoa da frente: "em que posição você está?". Essa pessoa também não sabe, e faz a mesma pergunta para a da frente. E assim por diante, até chegar à primeira pessoa da fila, que vê a bilheteria e responde, sem perguntar a ninguém: "estou na posição 1".

Agora as respostas voltam: a segunda pessoa ouve "1" e diz "então eu sou a 2"; a terceira ouve "2" e diz "sou a 3"… até a resposta chegar na Ana.

Essa história tem as duas partes de toda recursão:

• Caso base: a situação em que a resposta é imediata, sem perguntar a ninguém (a primeira pessoa da fila). É o que para a recursão.
• Passo recursivo: fazer a mesma pergunta para um problema um pouco menor (a pessoa da frente) e usar a resposta ("a dela + 1").

Primeiro exemplo: contagem regressiva

public class Main {
    static void contagemRegressiva(int n) {
        if (n == 0) {
            System.out.println("Fogo!");
            return;
        }
        System.out.println(n);
        contagemRegressiva(n - 1);
    }

    public static void main(String[] args) {
        contagemRegressiva(3);
    }
}

$ javac Main.java && java Main
3
2
1
Fogo!

if (n == 0) { … return; }

O caso base: quando a contagem chega a zero, imprime "Fogo!" e para. Sem ele, a contagem nunca terminaria.

System.out.println(n);

O trabalho de cada chamada: mostrar o número atual.

contagemRegressiva(n - 1);

O passo recursivo: o método chama a si mesmo com um problema menor (n - 1). É isso que garante que, mais cedo ou mais tarde, o caso base vai ser alcançado.

O que acontece por baixo: contagemRegressiva(3) imprime 3 e chama contagemRegressiva(2), que imprime 2 e chama contagemRegressiva(1), que imprime 1 e chama contagemRegressiva(0), que imprime "Fogo!" e retorna. Cada chamada é uma execução separada do método, com o seu próprio n: são quatro variáveis n diferentes, uma por chamada (lembre de Escopo: parâmetros vivem uma chamada).

public class Main {
    static int somar(int n) {
        // caso base

        // passo recursivo
        return 0;
    }

    public static void main(String[] args) {
        System.out.println("soma(5) = " + somar(5));
        System.out.println("soma(100) = " + somar(100));
    }
}

public class Main {
    static int somar(int n) {
        if (n == 0) {
            return 0;
        }
        return n + somar(n - 1);
    }

    public static void main(String[] args) {
        System.out.println("soma(5) = " + somar(5));
        System.out.println("soma(100) = " + somar(100));
    }
}

O fatorial

O fatorial de um número (escrito n!) é a multiplicação de todos os inteiros de 1 até ele: 5! = 5 × 4 × 3 × 2 × 1 = 120. Ele é o exemplo clássico de recursão porque a própria definição já é recursiva:

• 1! = 1 (e 0! = 1) → caso base.
• n! = n × (n − 1)! → o fatorial de 5 é 5 vezes o fatorial de 4.

public class Main {
    static long fatorial(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * fatorial(n - 1);
    }

    public static void main(String[] args) {
        System.out.println("5! = " + fatorial(5));
        System.out.println("10! = " + fatorial(10));
        System.out.println("20! = " + fatorial(20));
        System.out.println("21! = " + fatorial(21));
    }
}

$ javac Main.java && java Main
5! = 120
10! = 3628800
20! = 2432902008176640000
21! = -4249290049419214848      « estourou o long: veja o aviso abaixo

O tipo de retorno é long porque o fatorial cresce muito rápido: 13! já não cabe num int. Mesmo o long só aguenta até 20!; o 21! passa do limite e "dá a volta" para um número negativo, sem nenhum aviso. É o overflow que você viu em int, long, short, byte. Para números maiores, existe o BigInteger (veja BigDecimal e Dinheiro).

Passo a passo: a pilha de chamadas

Para enxergar o que o Java faz, a Ana acrescentou printlns e um recuo que aumenta a cada nível:

public class Main {
    static long fatorial(int n, String recuo) {
        System.out.println(recuo + "fatorial(" + n + ") começou");
        if (n <= 1) {
            System.out.println(recuo + "fatorial(" + n + ") devolve 1  « caso base");
            return 1;
        }
        long resultado = n * fatorial(n - 1, recuo + "   ");
        System.out.println(recuo + "fatorial(" + n + ") devolve " + resultado);
        return resultado;
    }

    public static void main(String[] args) {
        System.out.println("Resultado: " + fatorial(4, ""));
    }
}

$ javac Main.java && java Main
fatorial(4) começou
   fatorial(3) começou
      fatorial(2) começou
         fatorial(1) começou
         fatorial(1) devolve 1  « caso base
      fatorial(2) devolve 2
   fatorial(3) devolve 6
fatorial(4) devolve 24
Resultado: 24

Leia a saída como uma escada:

1. Descida: fatorial(4) não sabe a resposta; ele precisa de fatorial(3) e fica esperando. O mesmo acontece com 3 e com 2. Cada chamada em espera fica guardada numa estrutura da JVM chamada pilha de chamadas (call stack), uma em cima da outra, como pratos empilhados.
2. Caso base: fatorial(1) responde 1 na hora, sem chamar ninguém.
3. Subida: as respostas voltam, de cima para baixo da pilha. fatorial(2) recebe 1 e devolve 2 × 1 = 2; fatorial(3) devolve 3 × 2 = 6; fatorial(4) devolve 4 × 6 = 24.

Fibonacci (e por que ele é lento)

A sequência de Fibonacci começa com 0 e 1, e cada número seguinte é a soma dos dois anteriores: 0, 1, 1, 2, 3, 5, 8, 13, 21… A definição também é recursiva:

• fib(0) = 0 e fib(1) = 1 → dois casos base.
• fib(n) = fib(n − 1) + fib(n − 2) → duas chamadas recursivas.

A versão recursiva é quase uma cópia da definição. A Ana colocou um contador (um campo da classe) para saber quantas vezes o método é chamado:

public class Main {
    static long chamadas = 0;

    static long fib(int n) {
        chamadas++;
        if (n <= 1) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        for (int n = 0; n <= 10; n++) {
            System.out.print(fib(n) + " ");
        }
        System.out.println();

        int[] testes = {10, 20, 30};
        for (int n : testes) {
            chamadas = 0;
            long valor = fib(n);
            System.out.println("fib(" + n + ") = " + valor + " com " + chamadas + " chamadas");
        }
    }
}

$ javac Main.java && java Main
0 1 1 2 3 5 8 13 21 34 55
fib(10) = 55 com 177 chamadas
fib(20) = 6765 com 21891 chamadas
fib(30) = 832040 com 2692537 chamadas      « quase 2,7 milhões!

Para calcular fib(30), o método foi chamado 2.692.537 vezes. Cada vez que n aumenta 10, o número de chamadas fica mais de 100 vezes maior. O motivo é que o mesmo valor é recalculado de novo e de novo. Veja só o começo da árvore de fib(5):

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1)
│   │   │   └── fib(0)
│   │   └── fib(1)
│   └── fib(2)          « calculado de novo
│       ├── fib(1)
│       └── fib(0)
└── fib(3)              « toda esta parte é repetida
    ├── fib(2)          « e de novo
    │   ├── fib(1)
    │   └── fib(0)
    └── fib(1)

fib(3) é calculado duas vezes, fib(2) três vezes… Em fib(30), fib(2) é calculado mais de 500 mil vezes. A versão com um laço, que só guarda os dois últimos números, faz n passos e pronto:

public class Main {
    static long fibLaco(int n) {
        long anterior = 0, atual = 1;
        for (int i = 0; i < n; i++) {
            long proximo = anterior + atual;
            anterior = atual;
            atual = proximo;
        }
        return anterior;
    }

    public static void main(String[] args) {
        System.out.println("fib(10) = " + fibLaco(10));
        System.out.println("fib(30) = " + fibLaco(30));
        System.out.println("fib(90) = " + fibLaco(90));
    }
}

$ javac Main.java && java Main
fib(10) = 55
fib(30) = 832040
fib(90) = 2880067194370816120      « 90 voltas do laço; a recursiva levaria séculos

A lição não é "recursão é lenta": o fatorial recursivo faz só n chamadas, como o laço. O problema do Fibonacci é a recursão dupla que refaz o mesmo trabalho. Há técnicas para consertar isso guardando os resultados já calculados (o nome é memoização), que você poderá montar depois de aprender HashMap.

Quando a recursão não para: StackOverflowError

Cada chamada em espera ocupa um pedaço da pilha de chamadas, e essa pilha tem tamanho limitado. Se a recursão nunca chega ao caso base, as chamadas se empilham até a pilha transbordar (stack overflow). Veja o fatorial sem o caso base:

public class Main {
    static long fatorial(int n) {
        return n * fatorial(n - 1);
    }

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

Compila sem reclamar (o compilador não percebe que a recursão é infinita). Ao rodar:

$ javac Main.java && java Main
Exception in thread "main" java.lang.StackOverflowError
	at Main.fatorial(Main.java:3)
	at Main.fatorial(Main.java:3)
	at Main.fatorial(Main.java:3)
	at Main.fatorial(Main.java:3)
	at Main.fatorial(Main.java:3)
	« … mais 1019 linhas iguais …
$ java Main 2>&1 | wc -l
1025
$ java Main > /dev/null 2>&1; echo $?
1

Exception in thread "main"

O programa parou com um problema durante a execução, na thread principal (o main).

java.lang.StackOverflowError

"Erro de transbordamento da pilha". É um Error, não uma Exception comum: indica um problema grave, do qual o programa normalmente não se recupera.

at Main.fatorial(Main.java:3)

O stack trace (o "rastro da pilha"): cada linha é uma chamada que estava na pilha. Todas apontam para a linha 3, a da chamada recursiva. A JVM mostra no máximo 1024 linhas desse rastro; por isso o wc -l contou 1025 (a primeira linha + 1024).

código de saída 1

Como toda exceção não tratada, o programa termina com código 1. Veja O que são Exceções.

Até onde a recursão chega antes de estourar? Um método que só imprime o nível e desce mais um mostra isso (a saída tem milhares de linhas; o tail -1 mostra só a última):

$ java Main 2>/dev/null | tail -1
Nível 5388
$ java -Xss4m Main 2>/dev/null | tail -1
Nível 22479                « com uma pilha de 4 MB, cabem mais chamadas

Na máquina da Ana, a pilha padrão aguentou cerca de 5 mil chamadas desse método (o número muda um pouco a cada execução e depende do tamanho de cada chamada). A opção -Xss aumenta a pilha, mas isso só adia o problema: uma recursão infinita estoura qualquer pilha.

Recursão ou laço?

Tudo o que se faz com recursão dá para fazer com um laço, e vice-versa. O fatorial com for:

public class Main {
    static long fatorialLaco(int n) {
        long resultado = 1;
        for (int i = 2; i <= n; i++) {
            resultado = resultado * i;
        }
        return resultado;
    }

    public static void main(String[] args) {
        System.out.println("5! = " + fatorialLaco(5));
        System.out.println("20! = " + fatorialLaco(20));
    }
}

$ javac Main.java && java Main
5! = 120
20! = 2432902008176640000

Regra prática para quem está começando: use laço por padrão; use recursão quando o problema for naturalmente "uma coisa que contém coisas do mesmo tipo", como as pastas do computador da Ana, em que cada pasta pode ter outras pastas dentro. Você vai ver isso em Ler e Escrever Arquivos.

Quando dá errado

$ java Main
Exception in thread "main" java.lang.StackOverflowError
	at Main.fatorial(Main.java:3)
	at Main.fatorial(Main.java:3)
	at Main.fatorial(Main.java:3)
	« … mais 1021 linhas iguais …

$ java Main.java
5! = 120
10! = 3628800
20! = 2432902008176640000
21! = -4249290049419214848

Referência

Missão final: potência recursiva

public class Main {
    // escreva o método potencia aqui

    public static void main(String[] args) {
        System.out.println("2^10 = " + potencia(2, 10));
        System.out.println("3^4 = " + potencia(3, 4));
        System.out.println("5^0 = " + potencia(5, 0));
    }
}

public class Main {
    static long potencia(int base, int expoente) {
        if (expoente == 0) {
            return 1;
        }
        return base * potencia(base, expoente - 1);
    }

    public static void main(String[] args) {
        System.out.println("2^10 = " + potencia(2, 10));
        System.out.println("3^4 = " + potencia(3, 4));
        System.out.println("5^0 = " + potencia(5, 0));
    }
}

Exercícios

Resumo

• Um método recursivo chama a si mesmo para resolver uma versão menor do mesmo problema.
• Toda recursão precisa de um caso base (responde sem chamar ninguém) e de um passo recursivo que se aproxime dele.
• As chamadas em espera ficam na pilha de chamadas: a recursão desce até o caso base e as respostas sobem de volta.
• Sem caso base (ou sem diminuir o problema): StackOverflowError, com um stack trace de linhas repetidas apontando para a chamada recursiva.
• Fatorial recursivo é tranquilo; Fibonacci recursivo duplo é exponencialmente lento (2,7 milhões de chamadas para fib(30)).
• Prefira laços para repetições simples; use recursão para estruturas que contêm a si mesmas.