Denna djupgående handledning om rekursion i Java förklarar vad rekursion är med exempel, typer och relaterade begrepp. Den täcker också rekursion och iteration:
I våra tidigare handledningar 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 behåller en loopvariabel och upprepar en del av koden tills loopvariabeln uppfyller villkoret. När det gäller funktionsanrop har vi också utforskat det iterativa tillvägagångssättet för funktionsanrop.
I den här handledningen kommer vi att diskutera en annan metod för programmering, nämligen den rekursiva metoden.
Vad är rekursion i Java?
Rekursion är en process genom vilken en funktion eller en metod anropar sig själv om och om igen. Denna funktion som anropas 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.
Syntax för rekursion
Varje metod som implementerar rekursion har två grundläggande delar:
- Metodanrop som kan anropa sig själv, dvs. rekursivt.
- Ett villkor som stoppar rekursionen.
Observera att det krävs ett förvillkor för alla rekursiva metoder, eftersom om vi inte bryter rekursionen kommer den att fortsätta att köras i all oändlighet och resultera i ett stacköverflöde.
Den allmänna syntaxen för rekursion är följande:
methodName (T parameters...) { if (precondition == true) //precondition eller basvillkor { return result; } return methodName (T parameters...); //recursive call } Observera att förutsättningarna också kallas basvillkor. Vi kommer att diskutera mer om basvillkoret i nästa avsnitt.
Att förstå rekursion i Java
I det här avsnittet ska vi försöka förstå rekursionsprocessen och se hur den går till. Vi kommer att lära oss mer om basvillkoret, stack overflow och se hur ett visst problem kan lösas med rekursion och andra sådana detaljer.
Rekursion Grundvillkor
När vi skriver ett rekursivt program bör vi först ge en lösning för grundfallet. Därefter uttrycker vi det större problemet i termer av mindre problem.
Som en exempel, kan vi ta ett klassiskt problem som handlar om att beräkna faktorn av ett tal. Givet ett tal n måste vi hitta en faktorn av n som betecknas n!
Låt oss nu implementera programmet för att beräkna n-faktorn (n!) med hjälp av rekursion.
public class Main{ static int fact(int n) { if (n == 1) // basvillkor return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } Utgång
I det här programmet kan vi se att villkoret (n<=1) är grundvillkoret och när detta villkor är uppnått returnerar funktionen 1. Den andra delen av funktionen är det rekursiva anropet. Men varje gång den rekursiva metoden anropas minskas n med 1.
Vi kan alltså dra slutsatsen att värdet av n till slut kommer att bli 1 eller mindre än 1 och då kommer metoden att återge värdet 1. Detta basvillkor kommer att uppnås och funktionen kommer att sluta. Observera att värdet av n kan vara vad som helst så länge som det uppfyller basvillkoret.
Problemlösning med hjälp av rekursion
Den grundläggande idén med rekursion är att uttrycka ett större problem i form av mindre problem. Vi måste också lägga till ett eller flera grundvillkor för att kunna komma ut ur rekursionen.
Detta visades redan i exemplet med faktorn ovan. I det här programmet uttryckte vi faktorn n (n!) i termer av mindre värden och hade ett basvillkor (n <=1) så att när n når 1 kan vi avsluta den rekursiva metoden.
Stack Overflow fel i rekursion
Vi är medvetna om att när en metod eller funktion anropas lagras funktionens tillstånd på stacken och hämtas när funktionen återkommer. Stacken används även för den rekursiva metoden.
Men när det gäller rekursion kan ett problem uppstå om vi inte definierar basvillkoret eller om basvillkoret på något sätt inte uppnås eller utförs. Om denna situation uppstår kan stack overflow uppstå.
Låt oss ta nedanstående exempel på faktornotation.
Här har vi angett ett felaktigt grundvillkor, n==100.
public class Main { static int fact(int n) { if (n == 100) // grundvillkor som resulterar i 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 returnerar metoden 1 men rekursionen slutar inte. Värdet på n kommer att fortsätta att minska på obestämd tid eftersom det inte finns något annat villkor för att stoppa den. Detta kommer att fortsätta tills stacken rinner över.
Ett annat fall är när värdet på n <100. Även i detta fall kommer metoden aldrig att utföra basvillkoret och resultera i ett stack overflow.
Rekursionsexempel i Java
I det här avsnittet kommer vi att genomföra följande exempel med hjälp av rekursion.
#1) Fibonacci-serien med hjälp av 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.
Om n är det aktuella talet är det i allmänhet summan av (n-1) och (n-2). Eftersom det aktuella talet uttrycks i termer av tidigare tal kan vi uttrycka detta problem med hjälp av rekursion.
Programmet för att implementera Fibonacci-serien ges nedan:
public class Main { //metod för att beräkna fibonacci-serier 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; //utskrift av de 10 första siffrorna i fibonacci-serien System.out.println ("Fibonacci-serien: De 10 första siffrorna:"); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + " ");} } } Utgång
#2) Kontrollera om ett tal är en palindrom med hjälp av rekursion
En palindrom är en sekvens som är lika när den läses från vänster till höger eller från höger till vänster.
När vi ger oss av talet 121 ser vi att det är lika stort när vi läser det från vänster till höger och från höger till vänster. 121 är alltså en palindrom.
Låt oss ta ett annat tal, 1242. När vi läser det från vänster till höger är det 1242 och när vi läser det från höger till vänster är det 2421. Detta är alltså inte en palindrom.
Vi implementerar palindromprogrammet genom att vända på siffrorna i talen och rekursivt jämföra det givna talet med dess omvända representation.
Nedanstående program implementerar programmet för att kontrollera palindromer.
import java.io.*; import java.util.*; public class Main { // kontrollerar om numret endast innehåller en siffra 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 { // basvillkor; return if num=0 if (num == 0) { return revNum; } else { //callverktygsfunktion rekursivt revNum = isPalindrome_util(num / 10, revNum); } // Kontrollera om första siffran i num och revNum är lika om (num % 10 == revNum % 10) { // om ja, kommer revNum att flytta sig med num return revNum / 10; } else { // exit throw new Exception(); } } } //Metod för att kontrollera om ett givet tal är palindromt med hjälp av palindrom verktygsfunktion public static int isPalindrome(int num) throwsException { 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("Ja, det givna talet " + n + " är en palindrom."); } catch (Exception e) { System.out.println("Nej, det givna talet " + n + " är inte en palindrom."); } n = 1221; try { isPalindrome(n);System.out.println("Ja, det givna talet " + n + " är en palindrom."); } catch (Exception e) { System.out.println("Nej, det givna talet " + n + " är inte en palindrom."); } } } Utgång
#3) Omvänd strängrekursion Java
Med strängen "Hello" måste vi vända den så att den resulterande strängen blir "olleH".
Detta görs med hjälp av rekursion. Med utgångspunkt från det sista tecknet i strängen skrivs varje tecken ut rekursivt tills alla tecken i strängen är uttömda.
Nedanstående program använder rekursion för att vända en given sträng.
class String_Reverse { //recursiv metod för att vända en given sträng void reverseString(String str) { //basvillkor; återge om strängen är noll eller har 1 eller färre tecken if ((str==null)} } } } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("Den givna strängen: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("Den omvända strängen: "); obj.reverseString(inputstr); } } Utgång
#4) Binär sökning Java Rekursion
En binär sökalgoritm är en känd algoritm för sökning. I denna algoritm söker vi i en sorterad matris med n element efter det givna nyckelelementet. I början delar vi matrisen i två halvor genom att hitta det mittersta elementet i matrisen.
Beroende på om nyckelelementet är mitt i matrisen begränsar vi sedan sökningen till första eller andra halvan av matrisen. På så sätt upprepas samma process tills nyckelelementens plats har hittats.
Vi kommer att implementera denna algoritm med hjälp av rekursion här.
import java.util.*; class Binary_Search { // rekursiv binär sökning int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { //beräkna mitten av matrisen int mid = left + (right - left) / 2; // om nyckeln är vid mitten, returnera mid if (numArray[mid] == key) return mid; // om nyckel key) return binarySearch(numArray, left, mid - 1, key); // annars rekursivt söka ihöger delarray return binarySearch(numArray, mid + 1, right, key); } // inga element i matrisen, return -1 return -1; } } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //deklarera och skriva ut matrisen int numArray[] = { 4,6,12,16,22}; System.out.println("Den givna matrisen : " + Arrays.toString(numArray))); int len = numArray.length; //längden på matrisenint key = 16; //nyckel som ska sökas 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); } } Utgång
#5) Hitta minsta värde i matrisen med hjälp av rekursion
Med hjälp av rekursion kan vi också hitta det minsta värdet i matrisen.
Java-programmet för att hitta det minsta värdet i matrisen ges nedan.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //returnerar det första elementet om det bara finns ett element eller det minsta av arrayens element 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("Minsta element i matrisen: " + getMin(numArray, 0, n) + "\n"); } } Utgång
Detta är några exempel på rekursion. Förutom dessa exempel kan många andra problem i programvaran lösas med hjälp av rekursiva tekniker.
Rekursionstyper
Rekursion är av två typer beroende på när anropet görs till den rekursiva metoden.
De är:
#1) Återupprepning av svansen
När anropet till den rekursiva metoden är det sista uttalandet som utförs i den rekursiva metoden kallas det "Tail Recursion".
Vid svansrekursion utförs vanligtvis det rekursiva anropssignalen tillsammans med metodens retursignal.
Den allmänna syntaxen för svansrekursion anges nedan:
methodName ( T parameters ...){ { { if (base_condition == true) { return result; } return methodName (T parameters ...) //tail rekursion } #2) Huvudrekursion
Huvudrekursion är varje rekursiv metod som inte är en svansrekursion. Även allmän rekursion är alltså en framåtgående rekursion.
Syntaxen för huvudrekursion är följande:
methodName (T parameters...){ if (some_condition == true) { return methodName (T parameters...); } return result; } Rekursion och iteration i Java
| Rekursion | Iteration |
|---|---|
| Rekursion är en process där en metod anropar sig själv upprepade gånger tills ett grundvillkor är uppfyllt. | Iteration är en process genom vilken en del av koden utförs upprepade gånger ett begränsat antal gånger eller tills ett villkor är uppfyllt. |
| Är ansökan om funktioner. | Gäller för slingor. |
| Fungerar bra för mindre koder. | Fungerar bra för större koder. |
| Använder mer minne eftersom varje rekursivt anrop skjuts upp på stacken. | Jämförelsevis mindre minne används. |
| Svårt att felsöka och underhålla | Lättare att felsöka och underhålla |
| Leder till stack overflow om basvillkoret inte anges eller inte uppnås. | Kan exekveras i all oändlighet, men stoppar i slutändan exekveringen vid minnesfel. |
| Tidskomplexiteten är mycket hög. | Tidskomplexiteten är relativt låg. |
Ofta ställda frågor
F #1) Hur fungerar rekursion i Java?
Svar: Vid rekursion anropar den rekursiva funktionen sig själv upprepade gånger tills ett grundvillkor är uppfyllt. Minnet för den anropade funktionen skjuts upp på stacken överst på minnet för den anropande funktionen. För varje funktionsanrop görs en separat kopia av de lokala variablerna.
Q #2) Varför används rekursion?
Svar: Rekursion används för att lösa problem som kan delas upp i mindre problem och där 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 hjälp av en iterativ metod. Förutom de problem där tidskomplexiteten inte är ett problem, använd rekursion.
Q #3) Vilka är fördelarna med rekursion?
Svar:
Fördelarna med rekursion är bland annat:
- Rekursion minskar antalet överflödiga anrop av funktioner.
- Rekursion gör det lättare att lösa problem jämfört med iterativ metod.
F #4) Vilket är bäst - rekursion eller iteration?
Svar: Rekursion gör upprepade anrop tills basfunktionen är uppnådd, vilket innebär att det uppstår en minnesöverskott eftersom ett minne för varje funktionsanrop läggs på stacken.
Iteration å andra sidan har inte mycket minnesöverskott. Recursion är långsammare än iterativ metod. Recursion minskar kodens storlek medan iterativ metod gör koden stor.
Q #5) Vilka är fördelarna med rekursion jämfört med iterering?
Svar:
- Rekursion gör koden tydligare och kortare.
- Rekursion är bättre än den iterativa metoden för problem som Tower of Hanoi, trädtraversaler osv.
- Eftersom varje funktionsanrop innebär att minne läggs på stacken, använder rekursion mer minne.
- Recursionsprestanda är långsammare än den iterativa metoden.
Slutsats
Rekursion är ett mycket viktigt begrepp i programvara, oavsett programmeringsspråk. Rekursion används främst för att lösa problem med datastrukturer, t.ex. torn av Hanoi, trädtraversaler, länkade listor m.m. Även om det tar mer minne i anspråk gör rekursion koden enklare och tydligare.
Vi har undersökt allt om rekursion i den här handledningen. Vi har också implementerat många programmeringsexempel för att få en bättre förståelse för konceptet.