Recursie in Java - Tutorial met voorbeelden

recursion java tutorial with examples

Deze diepgaande zelfstudie over recursie in Java legt uit wat recursie is met voorbeelden, typen en gerelateerde concepten. Het omvat ook Recursion Vs Iteration:

In onze eerdere tutorials in Java hebben we de iteratieve benadering gezien waarbij we een lus declareren en vervolgens op een iteratieve manier door een datastructuur gaan door één element tegelijk te nemen.

We hebben ook de voorwaardelijke stroom gezien waarbij we weer één lusvariabele behouden en een stuk code herhalen totdat de lusvariabele aan de voorwaarde voldoet. Als het gaat om functieaanroepen, hebben we ook de iteratieve benadering voor functieaanroepen onderzocht.

​ Bekijk hier ALLE Java-tutorials.

In deze tutorial bespreken we een andere benadering van programmeren, namelijk de recursieve benadering.

Wat je leert:

• Wat is recursie in Java?
  • Recursie in Java begrijpen
    • Recursie-basisvoorwaarde
    • Probleemoplossing door middel van recursie
    • Stack Overflow-fout bij recursie
  • Recursievoorbeelden in Java
    • # 1) Fibonacci-serie met behulp van recursie
    • # 2) Controleer of een nummer een palindroom is met behulp van recursie
    • # 3) Omgekeerde stringrecursie Java
    • # 4) Binair zoeken Java-recursie
    • # 5) Zoek de minimumwaarde in de array met behulp van recursie
  • Recursietypes
    • # 1) Staartrecursie
    • # 2) Hoofdrecursie
• Recursie versus herhaling in Java
  • Veel Gestelde Vragen
• Gevolgtrekking
  • Aanbevolen literatuur

Wat is recursie in Java?

Recursie is een proces waarbij een functie of een methode zichzelf keer op keer aanroept. Deze functie die keer op keer direct of indirect wordt aangeroepen, wordt de “recursieve functie” genoemd.

We zullen verschillende voorbeelden zien om recursie te begrijpen. Laten we nu eens kijken naar de syntaxis van recursie.

Recursie-syntaxis

webservices c # interviewvragen

Elke methode die recursie implementeert, heeft twee basisonderdelen:

1. Methodeaanroep die zichzelf recursief kan noemen
2. Een voorwaarde die de recursie zal stoppen.

Merk op dat een voorwaarde nodig is voor elke recursieve methode, want als we de recursie niet verbreken, zal deze oneindig blijven werken en resulteren in een stack-overflow.

De algemene syntaxis van recursie is als volgt:

Merk op dat de voorwaarde ook wel basisvoorwaarde wordt genoemd. In de volgende sectie zullen we meer bespreken over de basisconditie.

Recursie in Java begrijpen

In deze sectie zullen we proberen het recursieproces te begrijpen en zien hoe het plaatsvindt. We zullen leren over de basisconditie, stack-overflow en zien hoe een bepaald probleem kan worden opgelost met recursie en andere soortgelijke details.

Recursie-basisvoorwaarde

Bij het schrijven van het recursieve programma moeten we eerst de oplossing voor het basisscenario bieden. Vervolgens drukken we het grotere probleem uit in termen van kleinere problemen.

Als een voorbeeld, we kunnen een klassiek probleem nemen van het berekenen van de faculteit van een getal. Gegeven een getal n, moeten we een faculteit van n vinden, aangeduid met n!

Laten we nu het programma implementeren om de n faculteit (n!) Te berekenen met behulp van recursie.

Uitvoer

In dit programma kunnen we zien dat de conditie (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.

We kunnen dus concluderen dat uiteindelijk de waarde van n 1 of kleiner wordt dan 1 en op dit punt zal de methode waarde 1 retourneren. Deze basisvoorwaarde wordt bereikt en de functie stopt. Merk op dat de waarde van n alles kan zijn, zolang deze maar voldoet aan de basisvoorwaarde.

Probleemoplossing door middel van recursie

Het basisidee achter het gebruik van recursie is om het grotere probleem uit te drukken in termen van kleinere problemen. We moeten ook een of meer basisvoorwaarden toevoegen, zodat we uit recursie kunnen komen.

Dit werd al aangetoond in het bovenstaande faculteitvoorbeeld. In dit programma hebben we de n faculteit (n!) Uitgedrukt in termen van kleinere waarden en hadden we een basisvoorwaarde (n<=1) so that when n reaches 1, we can quit the recursive method.

Stack Overflow-fout bij recursie

We zijn ons ervan bewust dat wanneer een methode of functie wordt aangeroepen, de status van de functie wordt opgeslagen op de stapel en wordt opgehaald wanneer de functie terugkeert. De stapel wordt ook gebruikt voor de recursieve methode.

Maar in het geval van recursie kan er een probleem optreden als we de basisvoorwaarde niet definiëren of als de basisvoorwaarde op de een of andere manier niet wordt bereikt of uitgevoerd. Als deze situatie zich voordoet, kan de stack overflow optreden.

Laten we het onderstaande voorbeeld van factoriële notatie eens bekijken.

Hier hebben we een verkeerde basisconditie gegeven, n == 100.

Dus als n> 100 de methode 1 retourneert, maar de recursie niet stopt. De waarde van n zal voor onbepaalde tijd afnemen omdat er geen andere voorwaarde is om het te stoppen. Dit gaat door totdat de stack overstroomt.

Een ander geval is wanneer de waarde van n<100. In this case, as well the method will never execute the base condition and result in a stack overflow.

Recursievoorbeelden in Java

In deze sectie zullen we de volgende voorbeelden implementeren met behulp van recursie.

# 1) Fibonacci-serie met behulp van recursie

De Fibonacci-serie wordt gegeven door,

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

De bovenstaande reeks laat zien dat het huidige element de som is van de vorige twee elementen. Ook is het eerste element in de Fibonacci-reeks 1.

Dus in het algemeen als n het huidige getal is, wordt het gegeven door de som van (n-1) en (n-2). Omdat het huidige element wordt uitgedrukt in termen van eerdere elementen, kunnen we dit probleem uitdrukken door middel van recursie.

Het programma om de Fibonacci-reeks te implementeren wordt hieronder gegeven:

Uitvoer

# 2) Controleer of een nummer een palindroom is met behulp van recursie

Een palindroom is een reeks die gelijk is als we hem van links naar rechts of van rechts naar links lezen.

Gegeven een getal 121, zien we dat wanneer we het van links naar rechts en van rechts naar links lezen, het gelijk is. Vandaar dat nummer 121 een palindroom is.

Laten we een ander nummer nemen, 1242. Als we het van links naar rechts lezen, is het 1242 en van rechts naar links gelezen als 2421. Dit is dus geen palindroom.

We implementeren het palindrome-programma door de cijfers van getallen om te draaien en recursief het gegeven getal te vergelijken met de omgekeerde weergave.

Het onderstaande programma implementeert het programma om het palindroom te controleren.

Uitvoer

# 3) Omgekeerde stringrecursie Java

Gegeven een string 'Hallo', moeten we deze omdraaien zodat de resulterende string 'olleH' is.

Dit gebeurt door middel van recursie. Beginnend vanaf het laatste teken in de string, drukken we elk teken recursief af totdat alle tekens in de string zijn uitgeput.

hoe float in java te declareren

Het onderstaande programma gebruikt recursie om een ​​bepaalde string om te keren.

Uitvoer

# 4) Binair zoeken Java-recursie

Een binair zoekalgoritme is een beroemd zoekalgoritme. In dit algoritme zoeken we, gegeven een gesorteerde array van n elementen, in deze array naar het gegeven sleutelelement. In het begin verdelen we de array in twee helften door het middenelement van de array te zoeken.

Afhankelijk van of de sleutel mid is, beperken we onze zoekopdracht in de eerste of tweede helft van de array. Op deze manier wordt hetzelfde proces herhaald totdat de locatie van de belangrijkste elementen is gevonden.

We zullen dit algoritme hier door middel van recursie implementeren.

Uitvoer

# 5) Zoek de minimumwaarde in de array met behulp van recursie

Met recursie kunnen we ook de minimumwaarde in de array vinden.

Het Java-programma om de minimumwaarde in de array te vinden, wordt hieronder gegeven.

Uitvoer

Dit zijn enkele voorbeelden van recursie. Naast deze voorbeelden kunnen veel andere problemen in de software worden geïmplementeerd met behulp van recursieve technieken.

Recursietypes

Er zijn twee soorten recursie, gebaseerd op het moment waarop de recursieve methode wordt aangeroepen.

Zij zijn:

# 1) Staartrecursie

Wanneer de aanroep van de recursieve methode de laatste instructie is die binnen de recursieve methode wordt uitgevoerd, wordt dit 'Tail Recursion' genoemd.

Bij staartrecursie wordt de recursieve call-instructie meestal samen met de return-instructie van de methode uitgevoerd.

De algemene syntaxis voor staartrecursie wordt hieronder gegeven:

programma om screenshots op de computer te maken

# 2) Hoofdrecursie

Hoofdrecursie is een recursieve benadering die geen staartrecursie is. Dus zelfs algemene recursie is voorwaartse recursie.

De syntaxis van hoofdrecursie is als volgt:

Recursie versus herhaling in Java

Veel Gestelde Vragen

V # 1) Hoe werkt recursie in Java?

Antwoord: Bij recursie roept de recursieve functie zichzelf herhaaldelijk aan totdat aan een basisvoorwaarde is voldaan. Het geheugen voor de aangeroepen functie wordt op de stapel geplaatst bovenaan het geheugen voor de aanroepende functie. Voor elke functieaanroep wordt een aparte kopie van lokale variabelen gemaakt.

Q # 2) Waarom wordt recursie gebruikt?

Antwoord: Recursie wordt gebruikt om die problemen op te lossen die in kleinere kunnen worden opgesplitst en het hele probleem kan worden uitgedrukt in termen van een kleiner probleem.

Recursie wordt ook gebruikt voor die problemen die te complex zijn om met een iteratieve aanpak op te lossen. Gebruik naast de problemen waarvoor tijdcomplexiteit geen probleem is, recursie.

Q # 3) Wat zijn de voordelen van recursie?

Antwoord:

De voordelen van recursie zijn onder meer:

1. Recursie vermindert het overbodig aanroepen van functies.
2. Recursie stelt ons in staat om problemen gemakkelijk op te lossen in vergelijking met de iteratieve benadering.

Vraag 4) Welke is beter: recursie of herhaling?

Antwoord: Recursie voert herhaalde oproepen uit totdat de basisfunctie is bereikt. Er is dus een geheugenoverhead omdat een geheugen voor elke functieaanroep naar de stapel wordt geduwd.

Iteratie daarentegen heeft niet veel geheugenoverhead. De uitvoering van recursie is langzamer dan de iteratieve benadering. Recursie vermindert de grootte van de code, terwijl de iteratieve benadering de code groot maakt.

Q # 5) Wat zijn de voordelen van recursie ten opzichte van iteratie?

Antwoord:

• Recursie maakt de code duidelijker en korter.
• Recursie is beter dan de iteratieve benadering voor problemen zoals de toren van Hanoi, boomdoorgangen, enz.
• Omdat bij elke functieaanroep geheugen naar de stapel wordt gepusht, gebruikt Recursion meer geheugen.
• De recursieprestaties zijn langzamer dan de iteratieve benadering.

Gevolgtrekking

Recursie is een zeer belangrijk concept in software, ongeacht de programmeertaal. Recursie wordt meestal gebruikt bij het oplossen van problemen met datastructuren, zoals torens van Hanoi, boomdoorgangen, gekoppelde lijsten, enz. Hoewel het meer geheugen kost, maakt recursie de code eenvoudiger en duidelijker.

We hebben in deze tutorial alles over recursie onderzocht. We hebben ook talloze programmeervoorbeelden geïmplementeerd voor een beter begrip van het concept.

​ Lees de Easy Java Training Series door.

Aanbevolen literatuur

• Recursie in C ++
• Java Iterator: leer iterators te gebruiken in Java met voorbeelden
• ListIterator-interface in Java met voorbeelden
• JAVA-zelfstudie voor beginners: 100+ praktische Java-videotutorials
• Java For Loop-zelfstudie met programmavoorbeelden
• Java While Loop - Tutorial met programmeervoorbeelden
• Java Do While Loop - Tutorial met voorbeelden
• Jagged Array in Java - Tutorial met voorbeelden