Meny

Rekursjon i Java - Veiledning med eksempler

  • Hoved
  • Annen
  • Rekursjon i Java - Veiledning med eksempler

recursion java tutorial with examples

Prøv Instrumentet Vårt For Å Eliminere Problemer

Denne grundige veiledningen om rekursjon i Java forklarer hva som er rekursjon med eksempler, typer og relaterte konsepter. Det dekker også Recursion Vs Iteration:

Fra våre tidligere opplæringsprogrammer i Java har vi sett den iterative tilnærmingen der vi erklærer en løkke og deretter krysse gjennom en datastruktur på en iterativ måte ved å ta ett element om gangen.

help desk tekniker intervju spørsmål og svar

Vi har også sett den betingede flyten der vi igjen holder en sløyfevariabel og gjentar et stykke kode til sløyfevariabelen oppfyller tilstanden. Når det gjelder funksjonssamtaler, utforsket vi også den iterative tilnærmingen for funksjonssamtaler.

=> Sjekk ALLE Java-opplæringsprogrammer her.

Rekursjon i Java

I denne veiledningen vil vi diskutere en annen tilnærming til programmering, dvs. rekursiv tilnærming.

Hva du vil lære:

Hva er rekursjon i Java?

Rekursjon er en prosess der en funksjon eller en metode kaller seg igjen og igjen. Denne funksjonen som kalles igjen og igjen, enten direkte eller indirekte, kalles 'rekursiv funksjon'.

Vi vil se forskjellige eksempler for å forstå rekursjon. La oss nå se syntaksen for rekursjon.

Rekursjonssyntaks

Enhver metode som implementerer Recursion har to grunnleggende deler:

  1. Metodekall som kan kalle seg selv dvs. rekursiv
  2. En forutsetning som vil stoppe rekursjonen.

Merk at en forutsetning er nødvendig for en hvilken som helst rekursiv metode, hvis vi ikke bryter rekursjonen, vil den fortsette å kjøre uendelig og resultere i en stabeloverløp.

Den generelle syntaksen for rekursjon er som følger:

methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call }

Merk at forutsetningen også kalles basistilstand. Vi vil diskutere mer om basistilstanden i neste avsnitt.

Forstå rekursjon i Java

I denne delen vil vi prøve å forstå rekursjonsprosessen og se hvordan den foregår. Vi vil lære om basistilstanden, stack overflow, og se hvordan et bestemt problem kan løses med rekursjon og andre slike detaljer.

Rekursjon Basistilstand

Mens vi skriver det rekursive programmet, bør vi først gi løsningen for basissaken. Så uttrykker vi det større problemet når det gjelder mindre problemer.

Som en eksempel, vi kan ta et klassisk problem med å beregne et talls faktor. Gitt et tall n, må vi finne et faktoria av n betegnet med n!

La oss nå implementere programmet for å beregne faktoren (n!) Ved hjelp av rekursjon.

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); } }

Produksjon

Rekursjon grunntilstand

I dette programmet kan vi se at tilstanden (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.

Dermed kan vi konkludere med at til slutt verdien av n blir 1 eller mindre enn 1, og på dette tidspunktet vil metoden returnere verdi 1. Denne basistilstanden vil bli nådd og funksjonen vil stoppe. Merk at verdien av n kan være hva som helst så lenge den tilfredsstiller grunntilstanden.

Problemløsing ved hjelp av rekursjon

Den grunnleggende ideen bak å bruke rekursjon er å uttrykke det større problemet når det gjelder mindre problemer. Vi må også legge til en eller flere grunnforhold slik at vi kan komme ut av rekursjon.

Dette ble allerede demonstrert i ovennevnte faktoreksempel. I dette programmet uttrykte vi n faktor (n!) I form av mindre verdier og hadde en grunntilstand (n<=1) so that when n reaches 1, we can quit the recursive method.

Stack Overflow Error In Recursion

Vi er klar over at når en hvilken som helst metode eller funksjon kalles, lagres funksjonen på bunken og blir hentet når funksjonen returnerer. Stakken brukes også til rekursiv metode.

Men i tilfelle rekursjon kan det oppstå et problem hvis vi ikke definerer basistilstanden eller når basistilstanden på en eller annen måte ikke er nådd eller utført. Hvis denne situasjonen oppstår, kan stabeloverløpet oppstå.

La oss se på eksemplet nedenfor om faktorotasjon.

Her har vi gitt feil grunntilstand, 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 vil metoden returnere 1, men rekursjon vil ikke stoppe. Verdien av n vil fortsette å reduseres på ubestemt tid, da det ikke er noen annen betingelse for å stoppe den. Dette vil fortsette til stakken renner over.

Et annet tilfelle vil være når verdien av n<100. In this case, as well the method will never execute the base condition and result in a stack overflow.

Rekursjonseksempler i Java

I denne delen vil vi implementere følgende eksempler ved hjelp av rekursjon.

# 1) Fibonacci-serien bruker rekursjon

Fibonacci-serien er gitt av,

1,1,2,3,5,8,13,21,34,55, ...

Ovennevnte sekvens viser at det nåværende elementet er summen av de to foregående elementene. Dessuten er det første elementet i Fibonacci-serien 1.

Så hvis generelt er n det nåværende tallet, blir det gitt av summen av (n-1) og (n-2). Ettersom det nåværende elementet uttrykkes i forhold til tidligere elementer, kan vi uttrykke dette problemet ved hjelp av rekursjon.

Programmet for å implementere Fibonacci-serien er gitt nedenfor:

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) + ' '); } } }

Produksjon

Fibonacci-serien - utgang

# 2) Kontroller om et tall er et palindrom ved bruk av rekursjon

En palindrom er en sekvens som er lik når vi leser den fra venstre til høyre eller høyre mot venstre.

Gitt et nummer 121 ser vi at når vi leser det fra venstre til høyre og høyre mot venstre, er det likt. Derfor er nummer 121 et palindrom.

La oss ta et annet tall, 1242. Når vi leser det fra venstre til høyre er det 1242, og når det leses fra høyre til venstre, leser det som 2421. Dermed er dette ikke et palindrom.

Vi implementerer palindrom-programmet ved å snu tallene og sammenligne det gitte tallet rekursivt med dets omvendte representasjon.

Programmet nedenfor implementerer programmet for å kontrollere 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.'); } } }

Produksjon

Sjekk om nummeret er et palindrom - utdata

# 3) Omvendt strengrekursjon Java

Gitt en streng 'Hello', må vi reversere den slik at den resulterende strengen blir 'olleH'.

Dette gjøres ved hjelp av rekursjon. Fra det siste tegnet i strengen skriver vi ut hvert tegn rekursivt til alle tegnene i strengen er oppbrukt.

Programmet nedenfor bruker rekursjon for å reversere en gitt streng.

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); } }

Produksjon

Omvendt strengrekursjon Java

# 4) Binær søk Java-rekursjon

En binær søkealgoritme er en kjent algoritme for søk. I denne algoritmen, gitt et sortert utvalg av n elementer, søker vi i denne matrisen etter det gitte nøkkelelementet. I begynnelsen deler vi matrisen i to halvdeler ved å finne midtelementet i matrisen.

Avhengig av om nøkkelen midt i begrenser vi søket vårt i første eller andre halvdel av matrisen. På denne måten gjentas den samme prosessen til plasseringen av nøkkelelementene er funnet.

Vi vil implementere denne algoritmen ved hjelp av rekursjon her.

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); } }

Produksjon

Binært søk Java - utdata

# 5) Finn minimumsverdi i array ved bruk av rekursjon

Ved å bruke rekursjon kan vi også finne minimumsverdien i matrisen.

Java-programmet for å finne minimumsverdien i matrisen er gitt nedenfor.

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) + ' '); } }

Produksjon

minimumsverdi i array rekursjon Java - output

Dette er noen av eksemplene på rekursjon. Bortsett fra disse eksemplene, kan mange andre problemer i programvaren implementeres ved hjelp av rekursive teknikker.

Rekursjonstyper

Rekursjon er av to typer basert på når anropet til den rekursive metoden.

De er:

# 1) Hale rekursjon

Når anropet til den rekursive metoden er den siste setningen som er utført i den rekursive metoden, kalles den “Tail Recursion”.

I halerekursjon blir den rekursive anropsuttalelsen vanligvis utført sammen med retursetningen til metoden.

Den generelle syntaksen for halerekursjon er gitt nedenfor:

methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion }

# 2) Head Recursion

Hoderekursjon er en hvilken som helst rekursiv tilnærming som ikke er en halenrekursjon. Så selv generell rekursjon er foran rekursjon.

Syntaksen for hodet rekursjon er som følger:

methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; }

Rekursjon mot Iterasjon i Java

RekursjonIterasjon
Tidskompleksitet er veldig høy.Tidskompleksitet er relativt på undersiden.
Rekursjon er en prosess der en metode kaller seg gjentatte ganger til en grunnvilkår er oppfylt.Iterasjon er en prosess der en kodebit utføres gjentatte ganger et begrenset antall ganger eller til en betingelse er oppfylt.
Er applikasjonen for funksjoner.Gjelder for løkker.
Fungerer bra for mindre kodestørrelse.Fungerer bra for større kodestørrelse.
Benytter mer minne når hvert rekursivt anrop skyves til bunkenForholdsvis mindre minne brukes.
Vanskelig å feilsøke og vedlikeholdeEnklere å feilsøke og vedlikeholde
Resultat i stabeloverløp hvis basistilstanden ikke er spesifisert eller ikke nådd.Kan utføre uendelig, men vil til slutt stoppe utførelsen med eventuelle minnefeil

ofte stilte spørsmål

Sp # 1) Hvordan fungerer Rekursjon i Java?

Svar: I rekursjon kaller den rekursive funksjonen seg gjentatte ganger til en basistilstand er oppfylt. Minnet for den anropte funksjonen skyves videre til bunken øverst i minnet for anropsfunksjonen. For hver funksjonsanrop lages en egen kopi av lokale variabler.

Q # 2) Hvorfor brukes rekursjon?

Svar: Rekursjon brukes til å løse de problemene som kan deles inn i mindre, og hele problemet kan uttrykkes i form av et mindre problem.

Rekursjon brukes også til de problemene som er for kompliserte til å løses ved hjelp av en iterativ tilnærming. I tillegg til problemene som tidskompleksitet ikke er et problem med, bruk rekursjon.

Q # 3) Hva er fordelene med rekursjon?

Svar:

Fordelene med rekursjon inkluderer:

  1. Rekursjon reduserer overflødig kall av funksjon.
  2. Rekursjon lar oss løse problemer enkelt sammenlignet med iterativ tilnærming.

Sp # 4) Hvilken er bedre - Rekursjon eller Iterasjon?

Svar: Rekursjon foretar gjentatte anrop til basefunksjonen er nådd. Dermed er det et minneoverhead når et minne for hver funksjonsanrop skyves videre til bunken.

Iterasjon har derimot ikke mye minne overhead. Rekursjonskjøring er tregere enn den iterative tilnærmingen. Rekursjon reduserer størrelsen på koden mens den iterative tilnærmingen gjør koden stor.

Q # 5) Hva er fordelene med rekursjon fremfor iterasjon?

Svar:

  • Rekursjon gjør koden tydeligere og kortere.
  • Rekursjon er bedre enn den iterative tilnærmingen for problemer som Tower of Hanoi, traversaler osv.
  • Ettersom hvert funksjonsanrop har minne presset til bunken, bruker Recursion mer minne.
  • Rekursjonsytelse er tregere enn den iterative tilnærmingen.

Konklusjon

Rekursjon er et veldig viktig konsept i programvare uavhengig av programmeringsspråk. Rekursjon brukes hovedsakelig til å løse datastrukturproblemer som tårn i Hanoi, tregjennomganger, koblede lister, etc. Selv om det tar mer minne, gjør rekursjon koden enklere og tydeligere.

Vi har utforsket alt om rekursjon i denne opplæringen. Vi har også implementert en rekke programmeringseksempler for bedre forståelse av konseptet.

=> Les gjennom Easy Java Training Series.

Anbefalt lesing

^