recursion java tutorial with examples
Aquest tutorial detallat sobre la recursió a Java explica què és la recursió amb exemples, tipus i conceptes relacionats. També cobreix la recursió contra la iteració:
Dels nostres tutorials anteriors a Java, hem vist l’enfocament iteratiu en què declarem un bucle i després recorrem una estructura de dades d’una manera iterativa prenent un element a la vegada.
També hem vist el flux condicional on de nou mantenim una variable de bucle i repetim un tros de codi fins que la variable de bucle compleixi la condició. Quan es tracta de trucades a funcions, també hem explorat l’enfocament iteratiu de les trucades a funcions.
=> Consulteu TOTS els tutorials de Java aquí.
En aquest tutorial, parlarem d’un enfocament diferent de la programació, és a dir, l’enfocament recursiu.
Què aprendreu:
- Què és la recursivitat a Java?
- Recursió vs Iteració a Java
- Conclusió
Què és la recursivitat a Java?
La recursió és un procés mitjançant el qual una funció o un mètode es criden una i altra vegada. Aquesta funció que es denomina una vegada i una altra directament o indirectament s'anomena 'funció recursiva'.
Veurem diversos exemples per entendre la recursivitat. Ara vegem la sintaxi de la recursivitat.
Sintaxi de recursió
Qualsevol mètode que implementi la recursió té dues parts bàsiques:
- Mètode de crida que es pot cridar a si mateix, és a dir, recursiu
- Una condició prèvia que aturarà la recursió.
Tingueu en compte que és necessària una condició prèvia per a qualsevol mètode recursiu, ja que, si no trenquem la recursió, continuarà funcionant infinitament i provocarà un desbordament de la pila.
La sintaxi general de la recursió és la següent:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Tingueu en compte que la condició prèvia també s’anomena condició base. A la secció següent, parlarem més sobre l’estat de la base.
Comprensió de la recursivitat a Java
En aquesta secció, intentarem entendre el procés de recursivitat i veure com té lloc. Aprendrem sobre l’estat de la base, el desbordament de la pila i veurem com es pot resoldre un problema concret amb recursivitat i altres detalls d’aquest tipus.
Estat de la base de recursió
En escriure el programa recursiu, primer hauríem de proporcionar la solució per al cas base. A continuació, expressem el problema més gran en termes de problemes més petits.
Com a exemple, podem prendre un problema clàssic de calcular el factorial d’un nombre. Donat un nombre n, hem de trobar un factorial de n denotat per n!
Ara implementem el programa per calcular el factorial n (n!) Mitjançant la recursió.
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); } }Sortida
En aquest programa, podem veure que la condició (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.
el millor reproductor de DVD gratuït per a DVD xifrats
Així, podem concloure que, finalment, el valor de n passarà a ser 1 o inferior a 1 i, en aquest moment, el mètode retornarà el valor 1. S'assolirà aquesta condició base i la funció s'aturarà. Tingueu en compte que el valor de n pot ser qualsevol, sempre que compleixi la condició base.
Resolució de problemes mitjançant recursivitat
La idea bàsica darrere de l’ús de la recursió és expressar el problema més gran en termes de problemes més petits. A més, hem d’afegir una o més condicions bàsiques per poder sortir de la recursivitat.
Això ja es va demostrar en l'exemple factorial anterior. En aquest programa, vam expressar el factorial n (n!) En termes de valors més petits i teníem una condició base (n<=1) so that when n reaches 1, we can quit the recursive method.
Error de desbordament de pila a la recursió
Som conscients que quan es diu qualsevol mètode o funció, l'estat de la funció s'emmagatzema a la pila i es recupera quan torna la funció. La pila també s’utilitza per al mètode recursiu.
Però en el cas de la recursivitat, es pot produir un problema si no definim la condició base o quan la condició base no s’arriba o s’executa d’alguna manera. Si es dóna aquesta situació, es pot produir el desbordament de la pila.
Considerem l’exemple següent de notació factorial.
Aquí hem donat una condició 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); } }Així, quan n> 100 el mètode retornarà 1, però la recursió no s'aturarà. El valor de n continuarà decrementant indefinidament ja que no hi ha cap altra condició que l’aturi. Això continuarà fins que es desbordi la pila.
Un altre cas serà quan el valor de n<100. In this case, as well the method will never execute the base condition and result in a stack overflow.
Exemples de recursivitat a Java
En aquesta secció, implementarem els exemples següents mitjançant recursivitat.
# 1) Sèrie Fibonacci mitjançant recursió
La sèrie de Fibonacci ve donada per,
1,1,2,3,5,8,13,21,34,55, ...
La seqüència anterior mostra que l'element actual és la suma dels dos elements anteriors. A més, el primer element de la sèrie de Fibonacci és 1.
Per tant, en general si n és el nombre actual, ve donat per la suma de (n-1) i (n-2). Com que l'element actual s'expressa en termes d'elements anteriors, podem expressar aquest problema mitjançant la recursió.
A continuació es mostra el programa per implementar la sèrie Fibonacci:
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) + ' '); } } } Sortida
# 2) Comproveu si un número és un palíndrom mitjançant la recursió
Un palíndrom és una seqüència que és igual quan el llegim d’esquerra a dreta o de dreta a esquerra.
Donat un número 121, veiem que quan el llegim d’esquerra a dreta i de dreta a esquerra és igual. Per tant, el número 121 és un palíndrom.
Agafem un altre número, 1242. Quan el llegim d’esquerra a dreta és el 1242 i, quan es llegeix de dreta a esquerra, es diu 2421. Per tant, no es tracta d’un palíndrom.
Implementem el programa de palíndrom invertint els dígits de nombres i comparem recursivament el nombre donat amb la seva representació invertida.
El programa següent implementa el programa per comprovar el palíndrom.
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.'); } } }Sortida
# 3) Recursió de cadena inversa Java
Tenint en compte una cadena 'Hola', hem de revertir-la perquè la cadena resultant sigui 'olleH'.
Això es fa mitjançant recursivitat. A partir de l'últim caràcter de la cadena, imprimim recursivament cada caràcter fins que s'esgotin tots els caràcters de la cadena.
El programa següent utilitza la recursió per invertir una cadena determinada.
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); } } Sortida
# 4) Recursió Java de cerca binària
Un algorisme de cerca binari és un famós algorisme de cerca. En aquest algorisme, donada una matriu ordenada de n elements, cerquem en aquesta matriu l’element clau donat. Al principi, dividim la matriu en dues meitats trobant l'element mitjà de la matriu.
Després, depenent de si la tecla central limitem la nostra cerca a la primera o segona meitat de la matriu. D'aquesta manera, es repeteix el mateix procés fins que es troba la ubicació dels elements clau.
Aquí implementarem aquest algorisme mitjançant la recursivitat.
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); } } Sortida
# 5) Cerqueu un valor mínim en matriu mitjançant la recursió
Mitjançant la recursió també podem trobar el valor mínim a la matriu.
A continuació es mostra el programa Java per trobar el valor mínim a la matriu.
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) + '
'); } }Sortida
sql plsql preguntes i respostes de l'entrevista
Aquests són alguns dels exemples de recursivitat. A part d’aquests exemples, es poden implementar molts altres problemes del programari mitjançant tècniques recursives.
Tipus de recursivitat
La recursió és de dos tipus en funció de quan es fa la trucada al mètode recursiu.
Ells són:
# 1) Recursió de la cua
Quan la crida al mètode recursiu és l'última sentència executada dins del mètode recursiu, s'anomena 'Recursió de la cua'.
En la recursió de cua, la sentència de trucada recursiva sol executar-se juntament amb la sentència de retorn del mètode.
A continuació es mostra la sintaxi general per a la recursió de la cua:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } # 2) Recursió del cap
La recursió del cap és qualsevol enfocament recursiu que no sigui una recursió de la cua. Per tant, fins i tot la recursió general és la recursiva per davant.
La sintaxi de la recursió del cap és la següent:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Recursió vs Iteració a Java
| Recursivitat | Iteració |
|---|---|
| La complexitat horària és molt alta. | La complexitat horària és relativament inferior. |
| La recursió és un procés on un mètode es crida a si mateix repetidament fins que es compleix una condició base. | La iteració és un procés mitjançant el qual un fragment de codi s'executa repetidament durant un nombre finit de vegades o fins que es compleix una condició. |
| És l'aplicació per a funcions. | És aplicable als bucles. |
| Funciona bé per a una mida de codi més petita. | Funciona bé per a mida de codi més gran. |
| Utilitza més memòria a mesura que cada trucada recursiva s’enfoca a la pila | Comparativament s’utilitza menys memòria. |
| Difícil de depurar i mantenir | Més fàcil de depurar i mantenir |
| Es produeix un desbordament de la pila si no s’especifica o no s’assoleix la condició base. | Es pot executar infinitament, però finalment s'aturarà l'execució amb qualsevol error de memòria |
Preguntes freqüents
P # 1) Com funciona la recursió a Java?
Resposta: En recursió, la funció recursiva es crida a si mateixa repetidament fins que es compleix una condició base. La memòria de la funció cridada s’empeny a la pila de la part superior de la memòria per a la funció de trucada. Per a cada trucada de funció, es fa una còpia separada de variables locals.
Q # 2) Per què s’utilitza la recursió?
Resposta: La recursivitat s’utilitza per resoldre aquells problemes que es poden desglossar en altres més petits i tot el problema es pot expressar en termes d’un problema més petit.
La recursivitat també s’utilitza per a aquells problemes massa complexos per resoldre’ls mitjançant un enfocament iteratiu. A més dels problemes per als quals la complexitat temporal no és un problema, utilitzeu la recursió.
Q # 3) Quins avantatges té la recursió?
Resposta:
Els avantatges de la recursió inclouen:
- La recursió redueix la crida de funció redundant.
- La recursió ens permet resoldre problemes fàcilment en comparació amb l’enfocament iteratiu.
Q # 4) Quin és millor: recursivitat o iteració?
Resposta: La recursió fa trucades repetides fins que s'assoleix la funció base. Per tant, hi ha una sobrecàrrega de memòria a mesura que s'enfoca una memòria per a cada trucada de funció a la pila.
D'altra banda, la iteració no té massa memòria. L’execució de la recursió és més lenta que l’enfocament iteratiu. La recursió redueix la mida del codi mentre que l’enfocament iteratiu fa que el codi sigui gran.
Q # 5) Quins avantatges té la recursió sobre la iteració?
Resposta:
- La recursió fa que el codi sigui més clar i curt.
- La recursió és millor que l’enfocament iteratiu per a problemes com la Torre de Hanoi, travessies d’arbres, etc.
- Com que cada trucada de funció té la memòria empesa a la pila, Recursion utilitza més memòria.
- El rendiment de la recursió és més lent que l’enfocament iteratiu.
Conclusió
La recursió és un concepte molt important en el programari, independentment del llenguatge de programació. La recursió s'utilitza principalment per resoldre problemes d'estructura de dades com torres de Hanoi, recorreguts d'arbres, llistes enllaçades, etc. Tot i que necessita més memòria, la recursió fa que el codi sigui més senzill i clar.
Hem explorat tot sobre la recursivitat en aquest tutorial. També hem implementat nombrosos exemples de programació per a una millor comprensió del concepte.
=> Llegiu la sèrie de formació Java fàcil.
Lectura recomanada
- Recursió en C ++
- Java Iterator: apreneu a utilitzar els iteradors a Java amb exemples
- Interfície ListIterator a Java amb exemples
- Tutorial JAVA per a principiants: més de 100 tutorials pràctics de vídeo Java
- Tutorial de Java For Loop amb exemples de programes
- Java While Loop: tutorial amb exemples de programació
- Java Do While Loop: tutorial amb exemples
- Matriu dentada a Java: tutorial amb exemples