Este titorial en profundidade sobre a recursión en Java explica o que é a recursividade con exemplos, tipos e conceptos relacionados. Tamén abarca Recursión vs Iteración:
Nos nosos titoriais anteriores en Java, vimos o enfoque iterativo no que declaramos un bucle e despois atravesamos unha estrutura de datos de forma iterativa tomando un elemento en un tempo.
Tamén vimos o fluxo condicional onde de novo mantemos unha variable de bucle e repetimos un anaco de código ata que a variable de bucle cumpra a condición. Cando se trata de chamadas de funcións, tamén exploramos o enfoque iterativo para as chamadas de funcións.
Neste titorial, discutiremos un enfoque diferente da programación, é dicir, o enfoque recursivo.
Que é a recursión en Java?
A recursión é un proceso polo cal unha función ou un método se chama a si mesmo unha e outra vez. Esta función que se chama unha e outra vez directa ou indirectamente denomínase “función recursiva”.
Veremos varios exemplos para entender a recursividade. Agora vexamos a sintaxe de recursividade.
Sintaxe de recursión
Calquera método que implemente a recursión ten dúas partes básicas:
- Chamada a un método que pode chamarse a si mesmo, é dicir, recursiva.
- Unha condición previa que deterá a recursividade.
Teña en conta que é necesaria unha condición previa para calquera método recursivo como, se non romper orecursividad, entón seguirá executando infinitamente e producirá un desbordamento da pila.
A sintaxe xeral da recursividade é a seguinte:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Teña en conta que a condición previa tamén se chama condición básica. Discutaremos máis sobre a condición base na seguinte sección.
Comprensión da recursividade en Java
Nesta sección, tentaremos comprender o proceso de recursividade e ver como ten lugar. Aprenderemos sobre a condición base, o desbordamento da pila e veremos como se pode resolver un problema particular coa recursividade e outros detalles similares.
Condición base de recursión
Mentres escribimos o programa recursivo, debemos primeiro proporcionar a solución para o caso base. Despois expresamos o problema máis grande en termos de problemas máis pequenos.
Como exemplo, podemos tomar un problema clásico de cálculo do factorial dun número. Dado un número n, temos que atopar un factorial de n denotado por n!
Agora imos implementar o programa para calcular o n factorial (n!) usando recursión.
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); } }Saída
Neste programa, podemos ver que a condición (n=1) é a condición base e cando se alcanza esta condición, a función devolve 1 A outra parte da función é a chamada recursiva. Pero cada vez que se chama ao método recursivo, n decreméntase en 1.
Así podemos concluír que, finalmente, o valor de n pasará a ser 1 ou menor que 1 e neste casopunto, o método devolverá o valor 1. Acadarase esta condición base e a función deterase. Teña en conta que o valor de n pode ser calquera cousa sempre que satisfaga a condición base.
Resolución de problemas usando recursión
A idea básica detrás do uso da recursión é expresar o problema máis grande en termos de problemas menores. Ademais, necesitamos engadir unha ou máis condicións base para que poidamos saír da recursividade.
Isto xa se demostrou no exemplo factorial anterior. Neste programa, expresamos o n factorial (n!) en termos de valores máis pequenos e tiña unha condición base (n =1) para que cando n chega a 1, poidamos saír do método recursivo.
Erro de desbordamento de pila en recursión
Somos conscientes de que cando se chama a calquera método ou función, o estado da función gárdase na pila e retírase cando a función volve. A pila utilízase tamén para o método recursivo.
Pero no caso da recursividade, pode ocorrer un problema se non definimos a condición base ou cando a condición base dalgún xeito non se alcanza nin se executa. Se se produce esta situación, pode producirse o desbordamento da pila.
Consideremos o seguinte exemplo de notación factorial.
Aquí demos unha condición base incorrecta, 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); } }Entón, cando n > 100 o método devolverá 1 pero a recursividade non parará. O valor de n seguirá diminuíndo indefinidamente como alínon é outra condición para detelo. Isto continuará ata que a pila se desborde.
Outro caso será cando o valor de n 100. Neste caso, tamén o método nunca executará a condición base e producirá un desbordamento de pila.
Exemplos de recursión en Java
Nesta sección, implementaremos os seguintes exemplos usando recursión.
#1) Serie de Fibonacci usando recursión
A serie de Fibonacci vén dada por,
1,1,2,3,5,8,13,21, 34,55,...
A secuencia anterior mostra que o elemento actual é a suma dos dous elementos anteriores. Ademais, o primeiro elemento da serie de Fibonacci é 1.
En xeral, se n é o número actual, entón vén dado pola suma de (n-1) e (n-2). Como o elemento actual se expresa en termos de elementos anteriores, podemos expresar este problema mediante a recursividade.
O programa para implementar a serie de Fibonacci dáse a continuación:
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) + " "); } } } Saída
#2) Comprobar se un número é un palíndromo usando recursión
Un palíndromo é unha secuencia que é igual cando léao de esquerda a dereita ou de dereita a esquerda.
Dado un número 121, vemos que cando o lemos de esquerda a dereita e de dereita a esquerda, é igual. De aí que o número 121 sexa un palíndromo.
Tomemos outro número, 1242. Cando o lemos de esquerda a dereita é 1242 e cando se le de dereita a esquerda lese como 2421. Polo tanto, este non é un palíndromo.
Nósimplementa o programa palíndromo invertendo os díxitos dos números e compara recursivamente o número dado coa súa representación invertida.
O programa de abaixo implementa o programa para comprobar 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."); } } }Saída
#3) Recurso de cadea inversa Java
Dada unha cadea “Ola” temos que invertila para que o a cadea resultante é “olleH”.
Isto faise mediante recursión. A partir do último carácter da cadea, imprimimos recursivamente cada carácter ata que se esgoten todos os caracteres da cadea.
O programa de abaixo usa a recursividade para inverter unha determinada cadea.
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); } } Saída
#4) Recurso de Java de busca binaria
Un algoritmo de busca binario é un algoritmo famoso para buscar. Neste algoritmo, dada unha matriz ordenada de n elementos, buscamos nesta matriz o elemento clave dado. Ao principio, dividimos a matriz en dúas metades atopando o elemento medio da matriz.
A continuación, dependendo de se a tecla central limitamos a nosa busca na primeira ou na segunda metade da matriz. Deste xeito repítese o mesmo proceso ata que se atopa a localización dos elementos clave.
Implementaremos este algoritmo usando recursividade aquí.
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); } } Saída
#5) Atopa o valor mínimo na matriz usando recursión
Utilizando a recursión tamén podemos atopar o valor mínimo na matriz.
OA continuación indícase o programa Java para atopar o valor mínimo na matriz.
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) + "\n"); } }Saída
Estes son algúns dos os exemplos de recursividade. Ademais destes exemplos, pódense implementar moitos outros problemas no software mediante técnicas recursivas.
Tipos de recursión
A recursión é de dous tipos en función do momento no que se fai a chamada a o método recursivo.
Son:
#1) Recursión de cola
Cando a chamada ao método recursivo é a última instrución executado dentro do método recursivo, chámase "Recursión de cola".
Na recursión de cola, a instrución de chamada recursiva adoita executarse xunto coa instrución de retorno do método.
O A sintaxe xeral para a recursividade da cola dáse a continuación:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } #2) Recursión da cabeza
A recursión da cabeza é calquera enfoque recursivo que non sexa unha recursión da cola. Polo tanto, incluso a recursividade xeral é a recursividad por diante.
A sintaxe da recursividade principal é a seguinte:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Recursión vs iteración en Java
| Recursión | Iteración |
|---|---|
| A recursión é un proceso no que un método se chama a si mesmo repetidamente ata que se cumpra unha condición base. | A iteración é un proceso polo cal unha peza de código se executa repetidamente durante un número finito de veces ou ata que se cumpra unha condición. |
| É a aplicación de funcións. | É aplicable. for loops. |
| Funciona ben paratamaño de código menor. | Funciona ben para tamaño de código maior. |
| Utiliza máis memoria a medida que cada chamada recursiva se envía á pila | Comparativamente menos memoria úsase. |
| Difícil de depurar e manter | Máis fácil de depurar e manter |
| Produce un desbordamento da pila se a base non se especifica ou non se alcanza. | Pódese executar infinitamente, pero finalmente deterá a execución con calquera erro de memoria |
| A complexidade do tempo é moi alta. | A complexidade do tempo é relativamente inferior. |
Preguntas frecuentes
P #1) Como funciona a recursividade en Java?
Resposta: Na recursión, a función recursiva chámase repetidamente ata que se cumpre unha condición base. A memoria para a función chamada envíase á pila na parte superior da memoria para a función de chamada. Para cada chamada de función, realízase unha copia separada das variables locais.
Q #2) Por que se usa a recursión?
Resposta: A recursividade úsase para resolver aqueles problemas que se poden dividir en outros máis pequenos e todo o problema pódese expresar en termos dun problema menor.
A recursión tamén se usa para aqueles problemas que son demasiado pequenos. complexo que se resolverá mediante un enfoque iterativo. Ademais dos problemas para os que a complexidade do tempo non é un problema, use a recursión.
P #3) Cales son os beneficios deRecursión?
Resposta:
Os beneficios da recurrencia inclúen:
- A recurrencia reduce as chamadas redundantes de función.
- A recursión permítenos resolver problemas facilmente en comparación co enfoque iterativo.
P #4) Cal é mellor: recursión ou iteración?
Resposta: Recursion fai chamadas repetidas ata que se alcanza a función base. Así, hai unha sobrecarga de memoria xa que unha memoria para cada chamada de función é empurrada á pila.
Por outra banda, a iteración non ten moita sobrecarga de memoria. A execución da recursividade é máis lenta que o enfoque iterativo. A recursividade reduce o tamaño do código mentres que o enfoque iterativo fai que o código sexa grande.
P #5) Cales son as vantaxes da recursión fronte á iteración?
Resposta:
- A recursión fai que o código sexa máis claro e curto.
- A recursividade é mellor que o enfoque iterativo para problemas como a Torre de Hanoi, a árbore percorridos, etc.
- Como cada chamada de función ten memoria empuxada na pila, Recursion usa máis memoria.
- O rendemento da recursión é máis lento que o enfoque iterativo.
Conclusión
A recursión é un concepto moi importante no software independentemente da linguaxe de programación. A recursión úsase principalmente para resolver problemas de estrutura de datos como torres de Hanoi, percorridos de árbores, listas vinculadas, etc. Aínda que leva máis memoria,a recursión fai que o código sexa máis sinxelo e claro.
Exploramos todo sobre a recursividade neste tutorial. Tamén implementamos numerosos exemplos de programación para unha mellor comprensión do concepto.