recursion java tutorial with examples
Este tutorial aprofundado sobre recursão em Java explica o que é recursão com exemplos, tipos e conceitos relacionados. Também cobre Recursão Vs Iteração:
Em nossos tutoriais anteriores em Java, vimos a abordagem iterativa em que declaramos um loop e, em seguida, percorremos uma estrutura de dados de maneira iterativa, pegando um elemento por vez.
Também vimos o fluxo condicional em que novamente mantemos uma variável de loop e repetimos um trecho de código até que a variável de loop atenda à condição. Quando se trata de chamadas de função, exploramos a abordagem iterativa para chamadas de função também.
=> Verifique TODOS os tutoriais Java aqui.
Neste tutorial, discutiremos uma abordagem diferente para a programação, ou seja, a abordagem recursiva.
O que você aprenderá:
- O que é recursão em Java?
- Recursão Vs Iteração em Java
- Conclusão
O que é recursão em Java?
Recursão é um processo pelo qual uma função ou método chama a si mesmo repetidamente. Esta função, que é chamada repetidamente, direta ou indiretamente, é chamada de “função recursiva”.
Veremos vários exemplos para entender a recursão. Agora vamos ver a sintaxe da recursão.
Sintaxe de recursão
Qualquer método que implemente recursão tem duas partes básicas:
- Chamada de método que pode chamar a si mesma, ou seja, recursiva
- Uma pré-condição que interromperá a recursão.
Observe que uma pré-condição é necessária para qualquer método recursivo, pois, se não quebrarmos a recursão, ele continuará rodando infinitamente e resultará em um estouro de pilha.
A sintaxe geral de recursão é a seguinte:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Observe que a pré-condição também é chamada de condição básica. Discutiremos mais sobre a condição básica na próxima seção.
Compreendendo a recursão em Java
Nesta seção, tentaremos entender o processo de recursão e ver como ele ocorre. Aprenderemos sobre a condição de base, estouro de pilha e veremos como um problema específico pode ser resolvido com recursão e outros detalhes.
Condição de base de recursão
Ao escrever o programa recursivo, devemos primeiro fornecer a solução para o caso base. Então, expressamos o problema maior em termos de problemas menores.
Como um exemplo, podemos pegar um problema clássico de cálculo do fatorial de um número. Dado um número n, temos que encontrar um fatorial de n denotado por n!
Agora vamos implementar o programa para calcular o fatorial n (n!) Usando recursão.
public class Main{ static int fact(int n) { if (n == 1) // base condition return 1; else return n*fact(n-1); } public static void main(String() args) { int result = fact(10); System.out.println('10! = ' + result); } }Resultado
Neste programa, podemos ver que a condição (n<=1) is the base condition and when this condition is reached, the function returns 1. The else part of the function is the recursive call. But every time the recursive method is called, n is decremented by 1.
Assim, podemos concluir que no final das contas o valor de n se tornará 1 ou menor que 1 e, neste ponto, o método retornará o valor 1. Essa condição base será alcançada e a função irá parar. Observe que o valor de n pode ser qualquer coisa, desde que satisfaça a condição básica.
Resolução de problemas usando recursão
A ideia básica por trás do uso de recursão é expressar o problema maior em termos de problemas menores. Além disso, precisamos adicionar uma ou mais condições de base para que possamos sair da recursão.
Isso já foi demonstrado no exemplo fatorial acima. Neste programa, expressamos o n fatorial (n!) Em termos de valores menores e tivemos uma condição de base (n<=1) so that when n reaches 1, we can quit the recursive method.
Erro de estouro de pilha na recursão
Estamos cientes de que quando qualquer método ou função é chamado, o estado da função é armazenado na pilha e é recuperado quando a função retorna. A pilha também é usada para o método recursivo.
Mas, no caso de recursão, pode ocorrer um problema se não definirmos a condição de base ou quando a condição de base de alguma forma não for alcançada ou executada. Se essa situação ocorrer, pode ocorrer o estouro da pilha.
Vamos considerar o exemplo abaixo de notação fatorial.
Aqui, fornecemos uma condição de base errada, n == 100.
public class Main { static int fact(int n) { if (n == 100) // base condition resulting in stack overflow return 1; else return n*fact(n-1); } public static void main(String() args) { int result = fact(10); System.out.println('10! = ' + result); } }Portanto, quando n> 100, o método retornará 1, mas a recursão não irá parar. O valor de n continuará diminuindo indefinidamente, pois não há outra condição para interrompê-lo. Isso continuará até o estouro da pilha.
Outro caso será quando o valor de n<100. In this case, as well the method will never execute the base condition and result in a stack overflow.
Exemplos de recursão em Java
Nesta seção, implementaremos os exemplos a seguir usando recursão.
# 1) Série Fibonacci usando recursão
A série Fibonacci é fornecida por,
1,1,2,3,5,8,13,21,34,55, ...
A seqüência acima mostra que o elemento atual é a soma dos dois elementos anteriores. Além disso, o primeiro elemento da série Fibonacci é 1.
Portanto, em geral, se n é o número atual, ele é dado pela soma de (n-1) e (n-2). Como o elemento atual é expresso em termos de elementos anteriores, podemos expressar esse problema usando recursão.
O programa de implementação da série Fibonacci é apresentado a seguir:
public class Main { //method to calculate fibonacci series static int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); } public static void main(String() args) { int number = 10; //print first 10 numbers of fibonacci series System.out.println ('Fibonacci Series: First 10 numbers:'); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + ' '); } } } Resultado
# 2) Verifique se um número é um palíndromo usando recursão
Um palíndromo é uma sequência igual quando o lemos da esquerda para a direita ou da direita para a esquerda.
Dado um número 121, vemos que quando o lemos da esquerda para a direita e da direita para a esquerda, ele é igual. Portanto, o número 121 é um palíndromo.
Vamos pegar outro número, 1242. Quando o lemos da esquerda para a direita, é 1242 e quando lido da direita para a esquerda é 2421. Portanto, este não é um palíndromo.
Implementamos o programa palíndromo invertendo os dígitos dos números e comparando recursivamente o número fornecido com sua representação invertida.
O programa abaixo implementa o programa para verificar o palíndromo.
import java.io.*; import java.util.*; public class Main { // check if num contains only one digit public static int oneDigit(int num) { if ((num >= 0) && (num <10)) return 1; else return 0; } //palindrome utility function public static int isPalindrome_util (int num, int revNum) throws Exception { // base condition; return if num=0 if (num == 0) { return revNum; } else { //call utility function recursively revNum = isPalindrome_util(num / 10, revNum); } // Check if first digit of num and revNum are equal if (num % 10 == revNum % 10) { // if yes, revNum will move with num return revNum / 10; } else { // exit throw new Exception(); } } //method to check if a given number is palindrome using palindrome utility function public static int isPalindrome(int num) throws Exception { if (num < 0) num = (-num); int revNum = (num); return isPalindrome_util(num, revNum); } public static void main(String args()) { int n = 1242; try { isPalindrome(n); System.out.println('Yes, the given number ' + n + ' is a palindrome.'); } catch (Exception e) { System.out.println('No, the given number ' + n + ' is not a palindrome.'); } n = 1221; try { isPalindrome(n); System.out.println('Yes, the given number ' + n + ' is a palindrome.'); } catch (Exception e) { System.out.println('No, the given number ' + n + ' is not a palindrome.'); } } }Resultado
# 3) Java de recursão de string reversa
Dada uma string “Hello”, temos que invertê-la para que a string resultante seja “olleH”.
Isso é feito usando recursão. Começando com o último caractere da string, imprimimos recursivamente cada caractere até que todos os caracteres da string se esgotem.
O programa a seguir usa recursão para reverter uma determinada string.
class String_Reverse { //recursive method to reverse a given string void reverseString(String str) { //base condition; return if string is null or with 1 or less character if ((str==null)||(str.length() <= 1)) System.out.println(str); else { //recursively print each character in the string from the end System.out.print(str.charAt(str.length()-1)); reverseString(str.substring(0,str.length()-1)); } } } class Main{ public static void main(String() args) { String inputstr = 'SoftwareTestingHelp'; System.out.println('The given string: ' + inputstr); String_Reverse obj = new String_Reverse(); System.out.print('The reversed string: '); obj.reverseString(inputstr); } } Resultado
# 4) Recursão Java de pesquisa binária
Um algoritmo de pesquisa binária é um algoritmo famoso de pesquisa. Neste algoritmo, dado um array ordenado de n elementos, procuramos neste array o elemento chave fornecido. No início, dividimos a matriz em duas metades, encontrando o elemento intermediário da matriz.
Então, dependendo se é a chave do meio, limitamos nossa pesquisa na primeira ou na segunda metade do array. Desta forma, o mesmo processo é repetido até que a localização dos elementos-chave seja encontrada.
qual é o melhor software de remoção de malware
Vamos implementar esse algoritmo usando recursão aqui.
import java.util.*; class Binary_Search { // recursive binary search int binarySearch(int numArray(), int left, int right, int key) { if (right >= left) { //calculate mid of the array int mid = left + (right - left) / 2; // if the key is at mid, return mid if (numArray(mid) == key) return mid; // if key key) return binarySearch(numArray, left, mid - 1, key); // Else recursively search in the right subarray return binarySearch(numArray, mid + 1, right, key); } // no elements in the array, return -1 return -1; } } class Main{ public static void main(String args()) { Binary_Search ob = new Binary_Search(); //declare and print the array int numArray() = { 4,6,12,16,22}; System.out.println('The given array : ' + Arrays.toString(numArray)); int len = numArray.length; //length of the array int key = 16; //key to be searched int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println('Element ' + key + ' not present'); else System.out.println('Element ' + key + ' found at index ' + result); } } Resultado
# 5) Encontre o valor mínimo na matriz usando recursão
Usando recursão, também podemos encontrar o valor mínimo na matriz.
O programa Java para encontrar o valor mínimo na matriz é fornecido abaixo.
import java.util.*; class Main { static int getMin(int numArray(), int i, int n) { //return first element if only one element or minimum of the array elements return (n == 1) ? numArray(i) : Math.min(numArray(i), getMin(numArray,i + 1 , n - 1)); } public static void main(String() args) { int numArray() = { 7,32,64,2,10,23 }; System.out.println('Given Array : ' + Arrays.toString(numArray)); int n = numArray.length; System.out.print('Minimum element of array: ' + getMin(numArray, 0, n) + '
'); } }Resultado
Esses são alguns exemplos de recursão. Além desses exemplos, muitos outros problemas no software podem ser implementados usando técnicas recursivas.
Tipos de recursão
A recursão é de dois tipos, com base em quando a chamada é feita para o método recursivo.
Eles estão:
# 1) Recursão de cauda
Quando a chamada ao método recursivo é a última instrução executada dentro do método recursivo, ela é chamada de “Recursão de cauda”.
Na recursão final, a instrução de chamada recursiva geralmente é executada junto com a instrução de retorno do método.
A sintaxe geral para recursão de cauda é fornecida abaixo:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } # 2) Recursão da cabeça
Recursão de cabeça é qualquer abordagem recursiva que não seja uma recursão de cauda. Portanto, mesmo a recursão geral está à frente da recursão.
A sintaxe da recursão principal é a seguinte:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Recursão Vs Iteração em Java
| Recursão | Iteração |
|---|---|
| A complexidade do tempo é muito alta. | A complexidade do tempo está relativamente no lado inferior. |
| Recursão é um processo em que um método chama a si mesmo repetidamente até que uma condição básica seja atendida. | Iteração é um processo pelo qual um trecho de código é executado repetidamente por um número finito de vezes ou até que uma condição seja atendida. |
| É o aplicativo para funções. | É aplicável para loops. |
| Funciona bem para códigos de tamanho menor. | Funciona bem para códigos de tamanho maior. |
| Utiliza mais memória conforme cada chamada recursiva é colocada na pilha | Comparativamente, menos memória é usada. |
| Difícil de depurar e manter | Mais fácil de depurar e manter |
| Resulta em estouro de pilha se a condição base não for especificada ou não for alcançada. | Pode ser executado infinitamente, mas acabará interrompendo a execução com quaisquer erros de memória |
perguntas frequentes
P # 1) Como funciona a recursão em Java?
Responda: Na recursão, a função recursiva chama a si mesma repetidamente até que uma condição básica seja satisfeita. A memória para a função chamada é colocada na pilha no topo da memória para a função de chamada. Para cada chamada de função, uma cópia separada das variáveis locais é feita.
Q # 2) Por que a recursão é usada?
Responda: A recursão é usada para resolver aqueles problemas que podem ser divididos em problemas menores e todo o problema pode ser expresso em termos de um problema menor.
A recursão também é usada para os problemas que são muito complexos para serem resolvidos com uma abordagem iterativa. Além dos problemas para os quais a complexidade do tempo não é um problema, use a recursão.
Q # 3) Quais são os benefícios da recursão?
Responda:
Os benefícios da recursão incluem:
- A recursão reduz a chamada redundante de função.
- A recursão nos permite resolver problemas facilmente quando comparada à abordagem iterativa.
P # 4) Qual é o melhor - Recursão ou Iteração?
Responda: A recursão faz chamadas repetidas até que a função base seja alcançada. Portanto, há uma sobrecarga de memória à medida que uma memória para cada chamada de função é colocada na pilha.
A iteração, por outro lado, não tem muita sobrecarga de memória. A execução da recursão é mais lenta do que a abordagem iterativa. A recursão reduz o tamanho do código, enquanto a abordagem iterativa torna o código grande.
Q # 5) Quais são as vantagens da recursão sobre a iteração?
Responda:
- A recursão torna o código mais claro e curto.
- A recursão é melhor do que a abordagem iterativa para problemas como a Torre de Hanói, travessias de árvores, etc.
- Como cada chamada de função tem memória empurrada para a pilha, a recursão usa mais memória.
- O desempenho da recursão é mais lento do que a abordagem iterativa.
Conclusão
A recursão é um conceito muito importante em software, independentemente da linguagem de programação. A recursão é usada principalmente na solução de problemas de estrutura de dados como torres de Hanói, travessias de árvores, listas vinculadas, etc. Embora exija mais memória, a recursão torna o código mais simples e claro.
Exploramos tudo sobre recursão neste tutorial. Também implementamos vários exemplos de programação para uma melhor compreensão do conceito.
=> Leia a série de treinamento Easy Java.
Leitura recomendada
- Recursão em C ++
- Java Iterator: Aprenda a usar Iteradores em Java com exemplos
- Interface ListIterator em Java com exemplos
- Tutorial de JAVA para iniciantes: mais de 100 tutoriais práticos em vídeo Java
- Java For Loop Tutorial com exemplos de programas
- Java While Loop - Tutorial com exemplos de programação
- Java Do While Loop - Tutorial com exemplos
- Jagged Array In Java - Tutorial com exemplos