Recursão é o processo de definir algo em termos deem si. No que se refere à programação Java, recursão é o atributo que permite que um método se chame. Um método que se autodenomina é considerado recursivo e o Java suporta recursão.
No começo, isso pode parecer um loop sem fim,e parece que nosso método nunca terminará. Isso pode ser verdade em alguns casos, mas, na prática, podemos verificar se uma determinada condição é verdadeira e, nesse caso, sair (retornar de) nosso método. O caso em que encerramos nossa recursão é chamado de caso base. Além disso, assim como em um loop, precisamos alterar algum valor e avançar de forma incremental para mais perto do nosso caso base.
Toda recursão deve ter as seguintes características:
- Um caso básico simples para o qual temos uma solução e um valor de retorno.
- Uma maneira de aproximar nosso problema do caso base. ou seja, uma maneira de eliminar parte do problema para obter um problema um pouco mais simples.
- Uma chamada recursiva que passa o problema mais simples de volta ao método.
Vantagens
O principal dos métodos recursivos é que eles podem serusado para criar versões mais claras e simples de vários algoritmos do que seus parentes iterativos. Por exemplo, o algoritmo de classificação QuickSort é bastante difícil de implementar de maneira iterativa.
Desvantagens
Versões recursivas de muitas rotinas podem executar umum pouco mais devagar que o equivalente iterativo, devido à sobrecarga adicional das chamadas de função adicionais. Muitas chamadas recursivas para um método podem causar uma pilha excedente. Como o armazenamento de parâmetros e variáveis locais, é possível que a pilha esteja esgotada. Se isso ocorrer, o sistema java run-time causará uma exceção. No entanto, você provavelmente não precisará se preocupar com isso, a menos que uma rotina recursiva corra solta.
Por exemplo:
int myFactorial(int integer) {
if( integer == 1) {
return 1;
}
else {
return(integer*(myFactorial(integer-1);
}
}A recursão da cauda é definida como ocorrendo quando ochamada recursiva está no final da instrução recursiva. Este não é o caso da minha solução fatorial acima. É útil notar quando um algoritmo usa recursão de cauda porque, nesse caso, o algoritmo geralmente pode ser reescrito para usar a iteração. De fato, o compilador (ou pelo menos deveria) converter o programa recursivo em um iterativo. Isso elimina o possível problema de estouro de pilha.
Este não é o caso da recursão da cabeça ou quandoa função se chama recursivamente em diferentes lugares, como na solução Towers of Hanoi. Obviamente, mesmo nesses casos, também poderíamos remover a recursão usando nossa própria pilha e simulando essencialmente como a recursão funcionaria.
No meu exemplo de fatorial acima do compiladorterá que chamar a função recursiva antes de fazer a multiplicação porque precisa resolver o valor (de retorno) da função antes de poder concluir a multiplicação. Portanto, a ordem de execução será a recursão "principal", ou seja, a recursão ocorre antes de outras operações.
Para converter isso em recursão de cauda, precisamos obtertoda a multiplicação terminou e foi resolvida antes de chamar recursivamente a função. Precisamos forçar a ordem de operação para que não esperemos a multiplicação antes de retornar. Se fizermos isso, o quadro da pilha pode ser liberado.
Anteriormente, você tinha visto nosso programa Java para calcular o fatorial de um número inteiro.
A maneira correta de fazer um fatorial recursivo da cauda é:
int factorial(int number) {
if(number == 0) {
return 1;
}
factorial_i(number, 1);
}
int factorial_i(int currentNumber, int sum) {
if(currentNumber == 1) {
return sum;
} else {
return factorial_i(currentNumber - 1, sum*currentNumber);
}
}Observe que no retorno de chamadafatorial_i (número atual - 1, soma * número atual); ambos os parâmetros são imediatamente solucionáveis. Podemos calcular qual é cada parâmetro sem aguardar o retorno de uma chamada de função recursiva. Este não é o caso da versão anterior do fatorial. Essa racionalização permite que o compilador minimize o uso da pilha, conforme explicado acima.
Você também pode pegar o número do usuário como um argumento de linha de comando.
Programa de Recursão Java
class Factorial{
int fact(int n){
int result;
if ( n ==1)
return 1;
result = fact (n-1) * n;
return result;
}
}
class Recursion{
public static void main (String args[]){
Factorial f =new Factorial();
System.out.println("Factorial of 3 is " + f.fact(3));
System.out.println("Factorial of 4 is " + f.fact(4));
System.out.println("Factorial of 5 is " + f.fact(5));
}
}Resultado
Explicação do código e saída Java
Se você não estiver familiarizado com métodos recursivos, a operação de facto() pode parecer um pouco confuso. Aqui está como isso funciona. Quando facto() é chamado com um argumento 1, a função retorna 1; caso contrário, ele retorna o produto de fato (n-1) * n. para avaliar esta expressão, facto() é chamado com n-1. Esse processo se repete até n é igual a 1 e as chamadas para o método começam a retornar.
Para entender melhor como o facto() método funciona, vamos seguir um pequeno exemplo. Ao calcular o fatorial de 3, a primeira chamada para facto() fará com que uma segunda chamada seja feita com um argumento 2. Esta chamada fará com que facto() ser chamado pela terceira vez com um argumento 2. Essa chamada retornará 1, que será chamada pela terceira vez com o argumento 1. Essa chamada retornará 1, que será multiplicada por 2 (o valor de n na segunda invocação). Esse resultado (que é 2) é retornado à invocação original de facto() e multiplique por 3 (o valor original de n) Isso gera a resposta, 6. Você pode achar interessante inserir println () declarações em facto() que mostrará em que nível cada chamada é e quais são as respostas intermediárias.
Quando um método se chama, novas variáveis locaise parâmetros são alocados de armazenamento na pilha e o código do método é executado com essas novas variáveis desde o início. Uma chamada recursiva não faz uma nova cópia do método. Somente os argumentos são novos. À medida que cada chamada recursiva retorna, as variáveis e parâmetros locais antigos são removidos da pilha e a execução é retomada no ponto da chamada dentro do método.
A seguir, aprenderemos como lidar com Matriz em Java.
Confira tutoriais mais úteis e diretrizes definitivas sobre programação Java aqui.
Comentários