Menu

Rekursion i Java - Vejledning med eksempler

recursion java tutorial with examples

Prøv Vores Instrument Til At Fjerne Problemer

Denne dybdegående tutorial om rekursion i Java forklarer, hvad der er rekursion med eksempler, typer og relaterede begreber. Det dækker også Recursion Vs Iteration:

Fra vores tidligere tutorials i Java har vi set den iterative tilgang, hvor vi erklærer en løkke og derefter krydser gennem en datastruktur på en iterativ måde ved at tage et element ad gangen.

Vi har også set den betingede strøm, hvor vi igen holder en loop-variabel og gentager et stykke kode, indtil loop-variablen opfylder betingelsen. Når det kommer til funktionsopkald, undersøgte vi også den iterative tilgang til funktionsopkald.

=> Tjek ALLE Java-tutorials her.

Rekursion i Java

I denne vejledning vil vi diskutere en anden tilgang til programmering, dvs. den rekursive tilgang.

Hvad du lærer:

Hvad er rekursion i Java?

Rekursion er en proces, hvor en funktion eller en metode kalder sig 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.

Rekursionsyntaks

Enhver metode, der implementerer Recursion, har to grundlæggende dele:

  1. Metodeopkald, der kan kalde sig selv dvs. rekursiv
  2. En forudsætning, der stopper rekursionen.

Bemærk, at en forudsætning er nødvendig for enhver rekursiv metode, da hvis vi ikke bryder rekursionen, vil den fortsætte med at køre uendeligt og resultere i et stackoverløb.

Den generelle syntaks for rekursion er som følger:

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

Bemærk, at forudsætningen også kaldes basistilstand. Vi vil diskutere mere om basistilstanden i det næste afsnit.

Forståelse af rekursion i Java

I dette afsnit vil vi forsøge at forstå rekursionsprocessen og se, hvordan den finder sted. Vi lærer om basistilstanden, stackoverløb og ser, hvordan et bestemt problem kan løses med rekursion og andre sådanne detaljer.

Rekursions basistilstand

Mens vi skriver det rekursive program, skal vi først give løsningen til basissagen. Derefter udtrykker vi det større problem i form af mindre problemer.

Som en eksempel, vi kan tage et klassisk problem med at beregne et tals faktor. Givet et tal n, er vi nødt til at finde en faktor af n betegnet med n!

Lad os nu implementere programmet til at beregne n faktor (n!) Ved hjælp af 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

Rekursions basistilstand

I dette program kan vi se, at betingelsen (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 konkludere, at værdien af ​​n i sidste ende bliver 1 eller mindre end 1, og på dette tidspunkt vil metoden returnere værdi 1. Denne basistilstand nås, og funktionen stopper. Bemærk, at værdien af ​​n kan være alt, så længe den opfylder basisbetingelsen.

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 er også nødt til at tilføje en eller flere basisbetingelser, så vi kan komme ud af rekursion.

Dette blev allerede demonstreret i ovenstående faktoreksempel. I dette program udtrykte vi n faktor (n!) I form af mindre værdier og havde en basistilstand (n<=1) so that when n reaches 1, we can quit the recursive method.

Stakoverløbsfejl i rekursion

Vi er opmærksomme på, 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 basistilstanden, eller når basistilstanden på en eller anden måde ikke er nået eller udført. Hvis denne situation opstår, kan stackoverløb opstå.

Lad os overveje nedenstående eksempel på faktoriel notation.

Her har vi givet en forkert basisbetingelse, 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 rekursion stopper ikke. Værdien af ​​n vil fortsætte med at falde på ubestemt tid, da der ikke er nogen anden betingelse for at stoppe det. Dette fortsætter, indtil stakken løber over.

Et andet tilfælde vil være, når værdien af ​​n<100. In this case, as well the method will never execute the base condition and result in a stack overflow.

Rekursionseksempler i Java

I dette afsnit implementerer vi følgende eksempler ved hjælp af rekursion.

# 1) Fibonacci-serie ved hjælp af rekursion

Fibonacci-serien er givet af,

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. Det første element i Fibonacci-serien er også 1.

Så hvis generelt er n det aktuelle tal, så er det givet ved summen af ​​(n-1) og (n-2). Da det aktuelle element udtrykkes 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 { //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

Fibonacci-serien - output

# 2) Kontroller, om et tal er et palindrom ved hjælp af rekursion

En palindrom er en sekvens, der er lige, når vi læser den fra venstre til højre eller højre mod venstre.

Med et nummer 121 ser vi, at når vi læser det fra venstre til højre og højre mod venstre, er det lige. Derfor er nummer 121 et palindrom.

Lad os tage et andet nummer, 1242. Når vi læser det fra venstre mod højre er det 1242, og når det læses fra højre til venstre, læses det som 2421. Dette er således ikke et palindrom.

Vi implementerer palindrom-programmet ved at vende cifrene i tal og sammenligne det givne tal rekursivt med dets omvendte repræsentation.

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

Produktion

Kontroller, om nummeret er et palindrom - output

# 3) Omvendt strengrekursion Java

Med en streng “Hej” er vi nødt til at vende den, så den resulterende streng er “olleH”.

Dette gøres ved hjælp af rekursion. Fra det sidste tegn i strengen udskriver vi hvert tegn rekursivt, indtil alle tegnene i strengen er opbrugt.

Nedenstående program bruger rekursion til at vende en given streng.

hvordan man åbner en .bin fil i windows
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

Omvendt strengrekursion Java

# 4) Binær søgning Java-rekursion

En binær søgealgoritme er en berømt algoritme til søgning. I denne algoritme, givet et sorteret array af n-elementer, søger vi i dette array for det givne nøgleelement. I begyndelsen deler vi arrayet i to halvdele ved at finde det midterste element i arrayet.

Afhængigt af om nøglen midt i begrænser vi vores søgning i den første eller anden halvdel af arrayet. På denne måde gentages den samme proces, indtil placeringen af ​​nøgleelementerne findes.

Vi implementerer denne algoritme ved hjælp af rekursion 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); } }

Produktion

Binær søgning Java - output

# 5) Find minimumsværdi i matrix ved hjælp af rekursion

Ved hjælp af rekursion kan vi også finde minimumsværdien i arrayet.

Java-programmet til at finde minimumsværdien i arrayet er angivet 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) + ' '); } }

Produktion

minimumsværdi i array rekursion Java - output

Dette er nogle af eksemplerne på rekursion. Bortset fra disse eksempler kan mange andre problemer i softwaren implementeres ved hjælp af rekursive teknikker.

Rekursionstyper

Rekursion er af to typer baseret på, hvornår opkaldet foretages til den rekursive metode.

De er:

# 1) Hale rekursion

Når opkaldet til den rekursive metode er den sidste sætning, der udføres inden for den rekursive metode, kaldes den 'Tail Recursion'.

I hale-rekursion udføres den rekursive opkaldsopgørelse normalt sammen med metoden om returneringserklæring.

Den generelle syntaks for halerekursion er angivet nedenfor:

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

# 2) Hovedrekursion

Hovedrekursion er enhver rekursiv tilgang, der ikke er en halerekursion. Så selv generel rekursion er foran rekursion.

Syntaksen for hovedrekursion er som følger:

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

Rekursion Vs Iteration I Java

RekursionIteration
Tidskompleksitet er meget høj.Tidskompleksitet er relativt på undersiden.
Rekursion er en proces, hvor en metode kalder sig gentagne gange, indtil en basisbetingelse er opfyldt.Iteration er en proces, hvorved et stykke kode udføres gentagne gange et begrænset antal gange, eller indtil en betingelse er opfyldt.
Er applikationen til funktioner.Gælder for sløjfer.
Fungerer godt til mindre kodestørrelse.Fungerer godt til større kodestørrelse.
Udnytter mere hukommelse, når hvert rekursivt opkald skubbes til stakkenDer anvendes relativt mindre hukommelse.
Svært at debugge og vedligeholdeLettere at debugge og vedligeholde
Resultater i stackoverløb, hvis basistilstanden ikke er specificeret eller ikke er nået.Kan udføre uendeligt, men vil i sidste ende stoppe udførelsen med eventuelle hukommelsesfejl

Ofte stillede spørgsmål

Spørgsmål nr. 1) Hvordan fungerer Rekursion i Java?

Svar: I rekursion kalder den rekursive funktion sig gentagne gange, indtil en basistilstand er opfyldt. Hukommelsen til den kaldte funktion skubbes videre til stakken øverst i hukommelsen til opkaldsfunktionen. For hvert funktionsopkald laves der en separat kopi af lokale variabler.

Q # 2) Hvorfor bruges rekursion?

Svar: Rekursion bruges til at løse de problemer, der kan opdeles i mindre, og 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 tilgang. 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 inkluderer:

  1. Rekursion reducerer overflødig kald af funktion.
  2. Rekursion giver os mulighed for let at løse problemer sammenlignet med iterativ tilgang.

Spørgsmål nr. 4) Hvilken er bedre - Rekursion eller gentagelse?

Svar: Rekursion foretager gentagne opkald, indtil basisfunktionen er nået. Der er således en hukommelsesoverhead, da en hukommelse for hvert funktionsopkald skubbes videre til stakken.

Iteration har derimod ikke meget hukommelsesomkostninger. Rekursionsudførelse er langsommere end den iterative tilgang. Rekursion reducerer størrelsen på koden, mens den iterative tilgang 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 tilgang til problemer som Tower of Hanoi, træpasninger osv.
  • Da hvert funktionsopkald har hukommelse skubbet videre til stakken, bruger Recursion mere hukommelse.
  • Rekursionsydelse er langsommere end den iterative tilgang.

Konklusion

Rekursion er et meget vigtigt koncept i software uanset programmeringssprog. Rekursion bruges mest til at løse datastrukturproblemer som tårne ​​i Hanoi, træpasninger, sammenkædede lister osv. Selvom det kræver mere hukommelse, gør rekursion koden enklere og klarere.

Vi har udforsket alt om rekursion i denne vejledning. Vi har også implementeret adskillige programmeringseksempler for en bedre forståelse af konceptet.

=> Læs gennem Easy Java Training Series.

Anbefalet læsning