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 decrescenteMé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.
.png)
.png)
