Exemplo de Recursividade - JAVA

Recursão é um método de programação no qual um função chama a si mesma.
A recursão é utilizada quando queremos resolver um subproblema do mesmo tipo menor.

• Se o problema é pequeno
• Então resolva o problema diretamente
• Senão
• Reduza o problema em um problema menor, chame novamente o método para o problema menor e volte ao problema original.

Chamando um método dentro dele mesmo:

A chamada de um método para ele mesmo, é igual a chamada de qualquer outro método, exemplo de método recursivo que calcula o fatorial n!:

O fatorial de um número é dado pela multiplicação de seus antecessores, ou seja, se n é igual 3, então seu fatorial será 3 * 2 * 1. O fatorial de 0! (zero) é igual a 1.

O método recursivo fica da seguinte forma:

Dentro de um método recursivo é muito importante definirmos como será a condição base para que o método pare a recursão, ou seja, como o método vai parar de se chamar.

Neste caso queremos que o método para de chamar ele mesmo, quando o valor que será calculado o fatorial for igual a 0 (zero), pois neste caso sabemos a resposta direta sem ter que fazer cálculos.

Testando o método recursivo:

Chamando o método fatorial(3), queremos calcular 3 * 2 * 1.
-> 3 * fatorial(2)  retorna (6)
-> -> 2 * fatorial(1)  retorna (2)
-> -> -> 1 * fatorial(0)  retorna (1)

Explicando o fluxo do programa:

1) O método fatorial recebe o valor de x igual a 3, verifica se x é igual a 0 (zero), como não é igual a 0 (zero), então calcula 3 multiplicado por fatorial(2), neste ponto estamos fazendo uma chamada recursiva.

2) O método fatorial recebe o valor de x igual a 2, verifica se x é igual a 0 (zero), como não é igual a 0 (zero), então calcula 2 multiplicado por fatorial(1).

3) O método fatorial recebe o valor de x igual a 1, verifica se x é igual a 0 (zero), como não é igual a 0 (zero), então calcula 1 multiplicado por fatorial(0).

4) O método fatorial recebe o valor de x igual a 0 (zero), verifica se x é igual a 0 (zero), então para a execução do método e retorna o valor 1.

5) Volta para o método fatorial(1) na linha 26 e faz a multiplicação de x que vale 1 pelo resultado do fatorial(0) que é 1, ou seja 1 * 1 e retorna o valor 1.

6) Volta para o método fatorial(2) na linha 26 e faz a multiplicação de x que vale 2 pelo resultado do fatorial(1) que é 1, ou seja 2 * 1 e retorna o valor 2.

7) Volta para o método fatorial(3) na linha 26 e faz a multiplicação de x que vale 3 pelo resultado do fatorial(2) que é 2, ou seja 3 * 2 e retorna o valor 6.

8) Volta para o método que chamou o fatorial(3), neste caso o método main na linha 7, guarda o resultado do fatorial(3) que é 6, dentro da variável resp, e imprime o resultado da variável resp na linha 8.

Outro exemplo de recursão: Ordem decrescente

Método recursivo que recebe um número x por parâmetro e imprime seu valor em ordem decrescente até 1.


Quando usamos recursão, precisamos definir o momento de parada, quando a função não deve ser mais chamada.

No caso do exemplo anterior queremos que o método não si chame novamente quando o x for igual a 0 (zero), porque queremos apenas os números entre [x ... 1]:

if(x == 0) return;

Agora precisamos definir o que nosso método deve fazer, neste caso deve imprimir o valor de x, e em seguida chama a si mesma diminuindo em 1 o valor de x.

System.out.println(x);
imprimirSequencia(x - 1);

A próxima vez que a função imprimirSequencia(int x) for chamada, o valor de x diminui 1 até chegar a 0 (zero) e parar a execução do código.