recursion java tutorial with examples
Denna djupgående handledning om rekursion i Java förklarar vad som är rekursion med exempel, typer och relaterade begrepp. Det täcker också Recursion Vs Iteration:
Från våra tidigare handledning i Java har vi sett det iterativa tillvägagångssättet där vi deklarerar en slinga och sedan går igenom en datastruktur på ett iterativt sätt genom att ta ett element i taget.
Vi har också sett det villkorliga flödet där vi återigen håller en slingvariabel och upprepar en bit kod tills slingvariabeln uppfyller villkoret. När det gäller funktionssamtal utforskade vi också det iterativa tillvägagångssättet för funktionssamtal.
=> Kontrollera ALLA Java-handledning här.
vid fel återupptas nästa i qtp
I denna handledning kommer vi att diskutera ett annat tillvägagångssätt för programmering, dvs Recursive.
Vad du kommer att lära dig:
- Vad är rekursion i Java?
- Rekursion mot Iteration i Java
- Slutsats
Vad är rekursion i Java?
Rekursion är en process genom vilken en funktion eller en metod kallar sig om och om igen. Denna funktion som kallas om och om igen antingen direkt eller indirekt kallas ”rekursiv funktion”.
Vi kommer att se olika exempel för att förstå rekursion. Låt oss nu se syntaxen för rekursion.
Rekursionssyntax
Varje metod som implementerar Rekursion har två grundläggande delar:
- Metodsamtal som kan kalla sig d.v.s. rekursivt
- En förutsättning som stoppar rekursionen.
Observera att en förutsättning är nödvändig för alla rekursiva metoder, eftersom om vi inte bryter rekursionen fortsätter den att köra oändligt och resulterar i ett stacköverflöde.
Den allmänna syntaksen för rekursion är som följer:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Observera att förutsättningen också kallas basvillkor. Vi kommer att diskutera mer om basvillkoren i nästa avsnitt.
Förstå rekursion i Java
I det här avsnittet kommer vi att försöka förstå rekursionsprocessen och se hur den sker. Vi kommer att lära oss om basvillkoret, stacköverflöde och se hur ett visst problem kan lösas med rekursion och andra sådana detaljer.
Rekursions basvillkor
När vi skriver det rekursiva programmet bör vi först tillhandahålla lösningen för basfallet. Sedan uttrycker vi det större problemet när det gäller mindre problem.
Som en exempel, vi kan ta ett klassiskt problem med att beräkna faktorn för ett tal. Med tanke på ett nummer n måste vi hitta ett faktoria av n betecknat med n!
Låt oss nu implementera programmet för att beräkna n faktoria (n!) Med rekursion.
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); } }Produktion
I detta program kan vi se att villkoret (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.
Således kan vi dra slutsatsen att värdet på n i slutändan blir 1 eller mindre än 1 och vid denna punkt kommer metoden att returnera värde 1. Detta basvillkor kommer att uppnås och funktionen kommer att stoppa. Observera att värdet på n kan vara vad som helst så länge det uppfyller grundvillkoret.
Problemlösning med rekursion
Grundidén bakom att använda rekursion är att uttrycka det större problemet i termer av mindre problem. Vi måste också lägga till en eller flera basvillkor så att vi kan komma ur rekursion.
Detta demonstrerades redan i ovanstående exempel på exempel. I detta program uttryckte vi n faktor (n!) I termer av mindre värden och hade ett grundvillkor (n<=1) so that when n reaches 1, we can quit the recursive method.
Stack Overflow Error In Recursion
Vi är medvetna om att när någon metod eller funktion anropas lagras funktionens tillstånd på stacken och hämtas när funktionen återvänder. Stapeln används också för den rekursiva metoden.
Men i fallet med rekursion kan ett problem uppstå om vi inte definierar basvillkoret eller när basvillkoret på något sätt inte nås eller utförs. Om denna situation inträffar kan stacköverflödet uppstå.
Låt oss överväga nedanstående exempel på faktornotation.
Här har vi gett fel basvillkor, 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); } }Så när n> 100 kommer metoden att returnera 1 men rekursion stoppar inte. Värdet på n fortsätter att minska på obestämd tid eftersom det inte finns något annat villkor för att stoppa det. Detta fortsätter tills stacken flyter över.
Ett annat fall kommer att vara när värdet på n<100. In this case, as well the method will never execute the base condition and result in a stack overflow.
Rekursionsexempel i Java
I det här avsnittet implementerar vi följande exempel med rekursion.
# 1) Fibonacci-serien använder rekursion
Fibonacci-serien ges av,
1,1,2,3,5,8,13,21,34,55, ...
Ovanstående sekvens visar att det aktuella elementet är summan av de två föregående elementen. Det första elementet i Fibonacci-serien är också 1.
Så i allmänhet om n är det aktuella talet, ges det av summan av (n-1) och (n-2). Eftersom det aktuella elementet uttrycks i termer av tidigare element kan vi uttrycka detta problem med rekursion.
Programmet för att implementera Fibonacci-serien ges nedan:
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) + ' '); } } } Produktion
# 2) Kontrollera om ett nummer är ett palindrom med rekursion
En palindrom är en sekvens som är lika när vi läser den från vänster till höger eller höger till vänster.
Med ett nummer 121 ser vi att när vi läser det från vänster till höger och höger till vänster är det lika. Därför är nummer 121 ett palindrom.
Låt oss ta ett annat nummer, 1242. När vi läser det från vänster till höger är det 1242 och när vi läser från höger till vänster läser det som 2421. Således är detta inte en palindrom.
Vi implementerar palindrom-programmet genom att vända siffrorna på siffror och jämföra rekursivt det angivna numret med dess omvända representation.
Programmet nedan implementerar programmet för att kontrollera palindromen.
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.'); } } }Produktion
# 3) Omvänd strängrekursion Java
Med tanke på strängen 'Hej' måste vi vända den så att den resulterande strängen blir 'olleH'.
Detta görs med rekursion. Från och med det sista tecknet i strängen skriver vi ut varje tecken rekursivt tills alla tecken i strängen är slut.
Programmet nedan använder rekursion för att vända en given sträng.
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); } } Produktion
# 4) Binär sökning Java-rekursion
En binär sökalgoritm är en berömd algoritm för sökning. I den här algoritmen, med en sorterad matris av n-element, söker vi i den här arrayen efter det angivna nyckelelementet. I början delar vi arrayen i två halvor genom att hitta mittelementet i arrayen.
Beroende på om nyckeln i mitten begränsar vi vår sökning i den första eller andra halvan av matrisen. På detta sätt upprepas samma process tills platsen för nyckelelementen hittas.
Vi implementerar denna algoritm med rekursion här.
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); } } Produktion
# 5) Hitta minimivärde i array med rekursion
Med rekursion kan vi också hitta minimivärdet i matrisen.
Java-programmet för att hitta minimivärdet i matrisen ges nedan.
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) + '
'); } }Produktion
Det här är några exempel på rekursion. Bortsett från dessa exempel kan många andra problem i programvaran implementeras med rekursiva tekniker.
Rekursionstyper
Rekursion är av två typer baserat på när samtalet görs till den rekursiva metoden.
Dom är:
# 1) Svansrekursion
När anropet till den rekursiva metoden är det sista uttalandet som utförs i den rekursiva metoden kallas det ”Tail Recursion”.
I svansrekursion utförs det rekursiva samtalsuttalandet vanligtvis tillsammans med metodens returuttalande.
Den allmänna syntaxen för svansrekursion ges nedan:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } # 2) Huvudrekursion
Huvudrekursion är varje rekursivt tillvägagångssätt som inte är en svansrekursion. Så även allmän rekursion ligger framför rekursion.
Syntax för huvudrekursion är som följer:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Rekursion mot Iteration i Java
| Rekursion | Iteration |
|---|---|
| Tidskomplexiteten är mycket hög. | Tidskomplexitet är relativt på undersidan. |
| Rekursion är en process där en metod kallar sig upprepade gånger tills ett grundvillkor är uppfyllt. | Iteration är en process genom vilken en kod kod upprepade gånger körs ett begränsat antal gånger eller tills ett villkor är uppfyllt. |
| Är applikationen för funktioner. | Gäller för öglor. |
| Fungerar bra för mindre kodstorlek. | Fungerar bra för större kodstorlek. |
| Använder mer minne när varje rekursivt samtal skjuts till stacken | Jämförelsevis mindre minne används. |
| Svårt att felsöka och underhålla | Lättare att felsöka och underhålla |
| Resultat i stacköverflöde om basvillkoret inte anges eller inte uppnås. | Kan köra oändligt men slutar slutligen körningen med minnesfel |
Vanliga frågor
F # 1) Hur fungerar Rekursion i Java?
Svar: I rekursion kallar den rekursiva funktionen sig upprepade gånger tills ett basvillkor är uppfyllt. Minnet för den anropade funktionen skjuts vidare till stacken högst upp i minnet för den anropande funktionen. För varje funktionsanrop görs en separat kopia av lokala variabler.
F # 2) Varför används rekursion?
Svar: Rekursion används för att lösa de problem som kan delas upp i mindre och hela problemet kan uttryckas i termer av ett mindre problem.
Rekursion används också för de problem som är för komplexa för att lösas med en iterativ metod. Förutom de problem för vilka tidskomplexitet inte är ett problem, använd rekursion.
F # 3) Vilka är fördelarna med rekursion?
Svar:
Fördelarna med rekursion inkluderar:
- Rekursion minskar redundant anrop av funktion.
- Rekursion gör att vi enkelt kan lösa problem jämfört med iterativt tillvägagångssätt.
F # 4) Vilken är bättre - Rekursion eller Iteration?
Svar: Rekursion gör upprepade samtal tills basfunktionen har uppnåtts. Således finns det ett minnesomkostnad då ett minne för varje funktionsanrop skjuts vidare till stacken.
Iteration å andra sidan har inte mycket minne över huvudet. Rekursionsexekvering är långsammare än iterativt tillvägagångssätt. Rekursion minskar storleken på koden medan den iterativa metoden gör koden stor.
F # 5) Vilka är fördelarna med rekursion jämfört med itteration?
Svar:
- Rekursion gör koden tydligare och kortare.
- Rekursion är bättre än det iterativa tillvägagångssättet för problem som Tower of Hanoi, trädkorsningar etc.
- Eftersom varje funktionsanrop har minne tryckt på stacken använder Recursion mer minne.
- Rekursionsprestanda är långsammare än det iterativa tillvägagångssättet.
Slutsats
Rekursion är ett mycket viktigt begrepp i programvara oavsett programmeringsspråk. Rekursion används mest för att lösa datastrukturproblem som torn i Hanoi, trädkorsningar, länkade listor etc. Även om det tar mer minne, gör rekursion koden enklare och tydligare.
Vi har utforskat allt om rekursion i denna handledning. Vi har också implementerat många programmeringsexempel för en bättre förståelse av konceptet.
=> Läs igenom Easy Java Training Series.
Rekommenderad läsning
- Rekursion i C ++
- Java Iterator: Lär dig att använda Iteratorer i Java med exempel
- ListIterator-gränssnitt i Java med exempel
- JAVA-handledning för nybörjare: 100+ praktiska Java-videohandledning
- Java för loop-handledning med programexempel
- Java While Loop - Handledning med programmeringsexempel
- Java Do While Loop - Handledning med exempel
- Jagged Array In Java - Handledning med exempel