Denne dybdegående vejledning om rekursion i Java forklarer, hvad rekursion er med eksempler, typer og relaterede begreber. Den dækker også rekursion vs. iteration:
Fra vores tidligere tutorials i Java har vi set den iterative tilgang, hvor vi erklærer en løkke og derefter gennemløber en datastruktur på en iterativ måde ved at tage et element ad gangen.
Vi har også set det betingede flow, hvor vi igen beholder en løkkevariabel og gentager et stykke kode, indtil løkkevariablen opfylder betingelsen. Når det kommer til funktionskald, har vi også udforsket den iterative tilgang til funktionskald.
I denne vejledning vil vi diskutere en anden tilgang til programmering, nemlig den rekursive tilgang.
Hvad er rekursion i Java?
Rekursion er en proces, hvor en funktion eller en metode kalder sig selv igen og igen. Denne funktion, der kaldes igen og igen enten direkte eller indirekte, kaldes "rekursiv funktion".
Vi vil se forskellige eksempler for at forstå rekursion. Lad os nu se syntaksen for rekursion.
Syntaks for rekursion
Enhver metode, der implementerer rekursion, har to grundlæggende dele:
- Metodeopkald, der kan kalde sig selv, dvs. rekursivt
- En forudsætning, der stopper rekursionen.
Bemærk, at en forudsætning er nødvendig for enhver rekursiv metode, da den vil blive ved med at køre i det uendelige, hvis vi ikke afbryder rekursionen, hvilket vil resultere i et stackoverløb.
Den generelle syntaks for rekursion er som følger:
methodName (T parameters...) { if (precondition == true) //precondition eller basisbetingelse { return result; } return methodName (T parameters...); //recursivt kald } Bemærk, at forudsætningen også kaldes grundbetingelsen. Vi vil tale mere om grundbetingelsen i næste afsnit.
Forståelse af rekursion i Java
I dette afsnit vil vi forsøge at forstå rekursionsprocessen og se, hvordan den foregår. Vi vil lære om basisbetingelsen, stackoverløb, og se, hvordan et bestemt problem kan løses med rekursion og andre sådanne detaljer.
Rekursion Grundbetingelse
Når vi skriver det rekursive program, skal vi først finde løsningen for grundtilfældet. Derefter udtrykker vi det større problem i form af mindre problemer.
Som en eksempel, kan vi tage et klassisk problem med at beregne faktorialen af et tal. Givet et tal n skal vi finde en faktorial af n, som betegnes n!
Lad os nu implementere programmet til at beregne n faktorial (n!) ved hjælp af rekursion.
public class Main{ static int fact(int n) { if (n == 1) // basisbetingelse return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } Udgang
I dette program kan vi se, at betingelsen (n<=1) er basisbetingelsen, og når denne betingelse er nået, returnerer funktionen 1. Den anden del af funktionen er det rekursive kald. Men hver gang den rekursive metode kaldes, dekreteres n med 1.
Vi kan således konkludere, at værdien af n i sidste ende vil blive 1 eller mindre end 1, og på dette tidspunkt vil metoden returnere værdien 1. Denne grundbetingelse vil være nået, og funktionen vil stoppe. Bemærk, at værdien af n kan være hvad som helst, så længe den opfylder grundbetingelsen.
Problemløsning ved hjælp af rekursion
Den grundlæggende idé bag brugen af rekursion er at udtrykke det større problem i form af mindre problemer. Vi skal også tilføje en eller flere basisbetingelser, så vi kan komme ud af rekursionen.
Dette blev allerede demonstreret i ovenstående faktoreksempel. I dette program udtrykte vi n-faktorialen (n!) i form af mindre værdier og havde en grundbetingelse (n <=1), så når n når 1, kan vi afslutte den rekursive metode.
Stack Overflow fejl i rekursion
Vi er klar over, at når en metode eller funktion kaldes, gemmes funktionens tilstand på stakken og hentes, når funktionen vender tilbage. Stakken bruges også til den rekursive metode.
Men i tilfælde af rekursion kan der opstå et problem, hvis vi ikke definerer basisbetingelsen, eller hvis basisbetingelsen på en eller anden måde ikke nås eller udføres. Hvis denne situation opstår, kan der opstå et stackoverløb.
Lad os se på nedenstående eksempel på faktorial notation.
Her har vi givet en forkert grundbetingelse, nemlig n==100.
public class Main { static int fact(int n) { if (n == 100) // grundbetingelse, der resulterer i stakoverløb 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 returnerer metoden 1, men rekursionen stopper ikke. Værdien af n vil blive ved med at falde i det uendelige, da der ikke er nogen anden betingelse for at stoppe den. Dette vil fortsætte, indtil stakken løber over.
Et andet tilfælde vil være, når værdien af n <100. I dette tilfælde vil metoden heller aldrig udføre grundbetingelsen og resultere i et stackoverløb.
Rekursion Eksempler i Java
I dette afsnit vil vi gennemføre følgende eksempler ved hjælp af rekursion.
#1) Fibonacci-serien ved hjælp af rekursion
Fibonacci-serien er givet ved,
1,1,2,3,5,8,13,21,34,55,…
Ovenstående sekvens viser, at det aktuelle element er summen af de to foregående elementer, og at det første element i Fibonacci-serien er 1.
Hvis n er det aktuelle tal, så er det generelt givet ved summen af (n-1) og (n-2). Da det aktuelle element er udtrykt i form af tidligere elementer, kan vi udtrykke dette problem ved hjælp af rekursion.
Programmet til implementering af Fibonacci-serien er angivet nedenfor:
public class Main { //metode til beregning af 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; //udskriv de første 10 tal i fibonacci-serien System.out.println ("Fibonacci-serie: De første 10 tal:"); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + " ");} } } Udgang
#2) Kontroller om et tal er et palindrom ved hjælp af rekursion
Et palindrom er en rækkefølge, der er ens, når vi læser den fra venstre mod højre eller fra højre mod venstre.
Hvis vi tager tallet 121, kan vi se, at når vi læser det fra venstre mod højre og fra højre mod venstre, er det lige stort, og derfor er tallet 121 et palindrom.
Lad os tage et andet tal, 1242. Når vi læser det fra venstre mod højre, er det 1242, og når vi læser det fra højre mod venstre, er det 2421. Det er altså ikke et palindrom.
Vi implementerer palindromprogrammet ved at vende tallets cifre om og rekursivt sammenligne det givne tal med dets omvendte repræsentation.
Nedenstående program implementerer programmet til at kontrollere palindromer.
import java.io.*; import java.util.*; public class Main { // kontrollere om num kun indeholder ét ciffer public static int oneDigit(int num) { if ((num>= 0) && (num <10))) return 1; else return 0; } //palindrome utility funktion public static int isPalindrome_util (int num, int revNum) throws Exception { // basisbetingelse; return if num=0 if (num == 0) { return revNum; } else { //callnyttefunktion rekursivt revNum = isPalindrome_util(num / 10, revNum); } // Kontroller om første ciffer i num og revNum er ens hvis (num % 10 == revNum % 10) { // hvis ja, vil revNum flytte sig med num return revNum / 10; } else { // exit throw new Exception(); } } } } //metode til at kontrollere, om et givet tal er palindromt ved hjælp af palindrom nyttefunktion 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("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("Ja, det givne tal " + n + " er et palindrom."); } catch (Exception e) { System.out.println("Nej, det givne tal " + n + " er ikke et palindrom."); } } } Udgang
#3) Omvendt string-rekursion Java
Med en streng "Hello" skal vi vende den om, så den resulterende streng bliver "olleH".
Dette gøres ved hjælp af rekursion. Vi starter med det sidste tegn i strengen og udskriver rekursivt hvert tegn, indtil alle tegn i strengen er udtømt.
Nedenstående program bruger rekursion til at omvende en given streng.
class String_Reverse { //recursiv metode til at vende en given streng void reverseString(String str) { //grundbetingelse; returnerer hvis strengen er nul eller har 1 eller færre tegn if ((str==null)} } } } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("Den givne streng: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("Den omvendte streng: "); obj.reverseString(inputstr); } } Udgang
#4) Binær søgning Java Rekursion
En binær søgealgoritme er en berømt algoritme til søgning. I denne algoritme søger vi i et sorteret array med n elementer efter det givne nøgleelement i arrayet. I begyndelsen deler vi arrayet i to halvdele ved at finde det midterste element i arrayet.
Derefter begrænser vi vores søgning til første eller anden halvdel af arrayet, afhængigt af om nøglen er midt i arrayet eller ej. På denne måde gentages den samme proces, indtil vi har fundet placeringen af nøgleelementerne.
Vi vil implementere denne algoritme ved hjælp af rekursion her.
import java.util.*; class Binary_Search { // rekursiv binær søgning int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { //beregn midten af arrayet int mid = left + (right - left) / 2; // hvis nøglen er ved midten, returneres mid if (numArray[mid] == key) return mid; // hvis key key) return binarySearch(numArray, left, mid - 1, key); // Ellers rekursiv søgning ihøjre delmatriale return binarySearch(numArray, mid + 1, right, key); } // ingen elementer i matrixen, return -1 return -1; } } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //deklarere og udskrive matrixen int numArray[] = { 4,6,12,16,22}; System.out.println("Den givne matrix : " + Arrays.toString(numArray))); int len = numArray.length; //længde af matrixenint key = 16; //nøgle, der skal søges int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println("Element " + key + " ikke til stede"); else System.out.println("Element " + key + " fundet ved indeks " + result); } } Udgang
#5) Find mindste værdi i array ved hjælp af rekursion
Ved hjælp af rekursion kan vi også finde den mindste værdi i arrayet.
Java-programmet til at finde den mindste værdi i arrayet er givet nedenfor.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //returnerer første element hvis kun ét element eller minimum af arrayelementerne 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("Mindste element i array: " + getMin(numArray, 0, n) + "\n"); } } Udgang
Dette er nogle af eksemplerne på rekursion. Ud over disse eksempler kan mange andre problemer i software implementeres ved hjælp af rekursive teknikker.
Rekursionstyper
Rekursion er af to typer baseret på, hvornår der kaldes til den rekursive metode.
De er:
#1) Hale-rekursion
Når kald til den rekursive metode er den sidste erklæring, der udføres inden for den rekursive metode, kaldes det "Tail Recursion".
Ved hale-rekursion udføres den rekursive call-erklæring normalt sammen med metodens return-erklæring.
Den generelle syntaks for hale-rekursion er angivet nedenfor:
methodName ( T parameters ...){ { { if (base_condition == true) { return result; } return methodName (T parameters ...) //tail rekursion } #2) Hoved-rekursion
Hovedrekursion er enhver rekursiv fremgangsmåde, der ikke er en hale-rekursion. Selv generel rekursion er således en fremadrettet rekursion.
Syntaksen for hovedrekursion er som følger:
methodName (T parameters...){ if (some_condition == true) { return methodName (T parameters...); } return result; } Rekursion og gentagelse i Java
| Rekursion | Iteration |
|---|---|
| Rekursion er en proces, hvor en metode kalder sig selv gentagne gange, indtil en grundbetingelse er opfyldt. | Iteration er en proces, hvor et stykke kode udføres gentagne gange et begrænset antal gange, eller indtil en betingelse er opfyldt. |
| Er ansøgningen om funktioner. | Gælder for sløjfer. |
| Fungerer godt til mindre kodestørrelse. | Fungerer godt til større kodestørrelse. |
| Bruger mere hukommelse, da hvert rekursivt kald skubbes til stakken | Der bruges forholdsvis mindre hukommelse. |
| Svært at fejlfinde og vedligeholde | Nemmere at fejlfinde og vedligeholde |
| Resulterer i stack overflow, hvis grundbetingelsen ikke er angivet eller ikke er nået. | Kan udføres i det uendelige, men vil i sidste ende stoppe udførelsen ved eventuelle hukommelsesfejl |
| Tidskompleksiteten er meget høj. | Tidskompleksiteten er relativt lav. |
Ofte stillede spørgsmål
Spørgsmål #1) Hvordan fungerer rekursion i Java?
Svar: Ved rekursion kalder den rekursive funktion sig selv gentagne gange, indtil en grundbetingelse er opfyldt. Hukommelsen for den kaldte funktion skubbes op på stakken øverst i den kaldende funktions hukommelse. For hvert funktionskald laves en separat kopi af de lokale variabler.
Q #2) Hvorfor bruges rekursion?
Svar: Rekursion bruges til at løse de problemer, der kan opdeles i mindre problemer, og hvor hele problemet kan udtrykkes i form af et mindre problem.
Rekursion bruges også til de problemer, der er for komplekse til at blive løst ved hjælp af en iterativ metode. Ud over de problemer, hvor tidskompleksitet ikke er et problem, skal du bruge rekursion.
Q #3) Hvad er fordelene ved rekursion?
Svar:
Fordelene ved rekursion er bl.a.:
- Rekursion reducerer overflødige kald af funktioner.
- Rekursion giver os mulighed for at løse problemerne let i forhold til den iterative metode.
Spørgsmål #4) Hvilken er bedst - rekursion eller gentagelse?
Svar: Recursion gentager opkald, indtil basisfunktionen er nået. Der er således et hukommelsesoverhead, da hukommelse for hvert funktionskald skubbes op på stakken.
Iteration har på den anden side ikke meget hukommelsesoverhead. Recursion er langsommere end den iterative fremgangsmåde. Recursion reducerer kodens størrelse, mens den iterative fremgangsmåde gør koden stor.
Q #5) Hvad er fordelene ved rekursion i forhold til gentagelse?
Svar:
- Rekursion gør koden klarere og kortere.
- Rekursion er bedre end den iterative metode til problemer som f.eks. tårnet i Hanoi, trætraversaler osv.
- Da der ved hvert funktionskald skal lægges hukommelse på stakken, bruger rekursion mere hukommelse.
- Recursion er langsommere end den iterative metode.
Konklusion
Rekursion er et meget vigtigt begreb i software uanset programmeringssprog. Rekursion bruges mest til at løse datastrukturproblemer som f.eks. tårne af Hanoi, trætraversaler, linkede lister osv. Selv om det kræver mere hukommelse, gør rekursion koden enklere og klarere.
Vi har udforsket alt om rekursion i denne tutorial. Vi har også implementeret adskillige programmeringseksempler for at opnå en bedre forståelse af konceptet.