Menu

Recursie in C ++

recursion c

Probeer Ons Instrument Voor Het Oplossen Van Problemen

Ontdek alles over recursie in C ++ met klassieke voorbeelden.

In onze vorige tutorial hebben we meer geleerd over functies in C ++.

Afgezien van het gebruik van de functies om de code in subeenheden op te splitsen en de code eenvoudiger en leesbaar te maken, zijn functies nuttig in verschillende andere toepassingen, waaronder het oplossen van problemen in realtime, wiskundige en statistische berekeningen.

Naarmate we complexere applicaties ontwikkelen in C ++, komen we veel vereisten tegen, zodat we verschillende speciale concepten van C ++ moeten gebruiken. Recursie is zo'n concept.

​ Bezoek hier voor de volledige C ++ Tutorials-lijst.

RECURSIE IN C ++

In deze tutorial zullen we meer leren over recursie, waar en waarom het wordt gebruikt, samen met enkele klassieke C ++ voorbeelden die recursie implementeren.

Wat je leert:

Wat is recursie?

Recursie is een proces waarbij een functie zichzelf aanroept. De functie die recursie implementeert of zichzelf aanroept, wordt een recursieve functie genoemd. Bij recursie roept de recursieve functie zichzelf keer op keer aan en gaat door totdat aan een eindvoorwaarde is voldaan.

De onderstaande afbeelding laat zien hoe recursie werkt:

Werking van recursie

Zoals we in het bovenstaande diagram zien, roept de hoofdfunctie een functie aan, funct (). Functie funct () roept zichzelf op zijn beurt binnen zijn definitie aan. Dit is hoe de recursie werkt. Dit proces van de functie die zichzelf aanroept, zal doorgaan totdat we een beëindigende voorwaarde bieden waardoor het zal eindigen.

Meestal bieden we codetak tijdens het implementeren van recursie, zodat we een voorwaarde bieden die recursie activeert en een andere om normale uitvoering uit te voeren.

Recursie-basisvoorwaarde

Wanneer recursie wordt uitgevoerd, wordt de oplossing voor de basisset of de afsluitbehuizing geboden en worden de oplossingen voor grotere problemen gebouwd op basis van de oplossingen voor kleinere problemen.

Laten we eens kijken naar een klassiek voorbeeld van recursie, de factoriële notatie​

We weten dat wiskundig gezien de faculteit van een getal n is:

n! = nxn-1x… .x0!
gezien het feit dat 0! = 1;

Dus faculteit voor n = 3 is 3! = 3 × 2!

3! = 3x2x1!
3! = 3x2x2x0!
3! = 3x2x1x1 = 6

Programmatisch kunnen we deze berekening dus als volgt uitdrukken:

​

Dus, zoals hierboven getoond, hebben we de bovenstaande berekening van een faculteit uitgedrukt in een recursieve functieaanroep. We zien dat als het getal n kleiner is dan of gelijk is aan 1, we 1 retourneren in plaats van een recursieve aanroep. Dit wordt de basisvoorwaarde / -geval voor de faculteit genoemd, waarmee de recursie kan worden gestopt.

Daarom bepaalt de basisvoorwaarde in feite hoe vaak een recursieve functie zichzelf moet aanroepen. Dit betekent dat we heel goed de faculteit van een groter getal kunnen berekenen door deze uit te drukken in kleinere getallen totdat de basisklasse is bereikt.

Hieronder is een perfect voorbeeld gegeven om de faculteit van een getal te berekenen:

​

Uitgang:

Voer het getal in waarvan de faculteit moet worden berekend: 10
10! = 3628800

In het bovenstaande voorbeeld implementeren we recursie. We nemen het getal waarvan de faculteit moet worden gevonden uit de standaardinvoer en geven het vervolgens door aan de faculteit.

In de faculteitfunctie hebben we de basisvoorwaarde gegeven als (n<=1). So, when the base case is reached, the function returns. Using this base case, we can calculate factorial of any number greater than 1.

Geheugentoewijzing voor de recursieve oproep

We weten dat wanneer een functieaanroep wordt gedaan, de status van de aanroepende functie wordt opgeslagen op de stapel en wanneer een functieaanroep is voltooid, wordt deze toestand hersteld zodat het programma kan doorgaan met uitvoeren.

Wanneer een recursieve functieaanroep wordt gedaan, wordt de toestand of het geheugen voor de aangeroepen functie toegewezen bovenop de toestand van de aanroepende functie en wordt voor elke recursieve functieaanroep een andere kopie van lokale variabelen gemaakt.

Wanneer de basisvoorwaarde is bereikt, keert de functie terug naar de aanroepfunctie en wordt het geheugen vrijgemaakt en gaat het proces verder.

Stack Overflow bij recursie

Wanneer recursie voor een onbeperkte tijd voortduurt, kan dit resulteren in een stack-overflow.

Wanneer kan recursie zo doorgaan? Een situatie is wanneer we de basisconditie niet specificeren. Een andere situatie is wanneer de basisconditie niet wordt bereikt tijdens het uitvoeren van een programma.

Bijvoorbeeld,we wijzigen het bovenstaande faculteitsprogramma en veranderen de basisconditie.

​

In de bovenstaande code hebben we de basisvoorwaarde gewijzigd in (n == 1000). Als we nu het getal n = 10 geven, kunnen we concluderen dat de basisvoorwaarde nooit zal bereiken. Op deze manier zal het geheugen op de stapel op een gegeven moment uitgeput raken, wat resulteert in een stapeloverloop.

Daarom moeten we bij het ontwerpen van recursieve programma's voorzichtig zijn met de basisconditie die we bieden.

Directe versus indirecte recursie

Tot dusverre hebben we bij recursie gezien dat de functie zichzelf aanroept. Dit is de directe recursie.

Er is een ander type recursie, namelijk indirecte recursie. Hierbij roept een functie een andere functie aan en dan roept deze functie de aanroepende functie aan. Als f1 en f2 twee functies zijn. Vervolgens callt f1 f2 en callt f2 op hun beurt f1. Dit is een indirecte recursie.

ik heb een vals e-mailadres nodig

L. et ons herzien ons faculteitsprogramma om directe recursie aan te tonen.

​

Uitgang:

Voer het getal in waarvan de faculteit moet worden berekend: 5
5! = 120

In het bovenstaande voorbeeld hebben we indirecte recursie laten zien. De hoofdfunctie roept factorial_a aan. Factorial_a roept factorial_b aan. Factorial_b roept op zijn beurt factorial_a aan. We zien dat de output van het programma niet wordt beïnvloed.

Recursie zonder staart en zonder staart

Een recursieve functie met een staart is een recursieve functie waarbij de laatste aanroep wordt uitgevoerd in de functie.

Bijvoorbeeld, overweeg dan de volgende functie.

​

In het bovenstaande voorbeeld is de weergave een recursieve functie met een staart, zodat het de laatste functieaanroep is.

Tailed-functies worden als beter beschouwd dan niet-tailed recursieve functies, omdat ze kunnen worden geoptimaliseerd door de compiler. De reden hiervoor is dat aangezien de recursieve aanroep met de staart de laatste instructie in de functie is, er geen code hoeft te worden uitgevoerd na deze aanroep.

Als resultaat is het opslaan van het huidige stapelframe voor de functie niet vereist.

Voors / tegens van recursie ten opzichte van iteratief programmeren

Recursieve programma's bieden compacte en schone code. Een recursief programma is een eenvoudige manier om programma's te schrijven. Er zijn enkele inherente problemen zoals faculteit, Fibonacci-reeks, torens van Hanoi, boomdoorgangen, enz. Die recursie vereisen om op te lossen.

Met andere woorden, ze worden efficiënt opgelost met recursie. Ze kunnen ook worden opgelost met iteratief programmeren met behulp van stapels of andere datastructuren, maar de kans bestaat dat ze complexer worden om te implementeren.

Probleemoplossend vermogen van recursieve en iteratieve programmering is hetzelfde. Recursieve programma's nemen echter meer geheugenruimte in beslag, omdat alle functieaanroepen op de stapel moeten worden opgeslagen totdat het basisscenario overeenkomt.

Recursieve functies hebben ook een tijdoverhead vanwege te veel functieaanroepen en retourwaarden.

Voorbeelden van recursie

Vervolgens zullen we enkele voorbeelden van recursief programmeren implementeren.

Fibonacci-serie

Fibonacci-reeks is de reeks die wordt gegeven als

0 1 1 2 3 5 8 13 ……

Zoals hierboven getoond, zijn de eerste twee getallen van Fibonacci-reeksen 0 en 1. Het volgende getal in de reeks is de som van de vorige twee getallen.

Laten we deze serie implementeren met behulp van recursie.

​

Uitgang:

Voer het aantal elementen voor de Fibonacci-reeks in: 10
Fibonacci-serie voor 10 nummers: 0 1 1 2 3 5 8 13 21 34

In dit voorbeeld hebben we een recursieve aanroep gebruikt om de Fibonacci-reeks te genereren. We zien dat de eerste twee nummers die constant zijn, direct worden afgedrukt en voor de volgende nummers in de reeks gebruiken we een recursieve functie.

Palindroom

Een palindroomgetal is een getal dat, wanneer het in omgekeerde richting wordt gelezen, hetzelfde is als gelezen in een richting van links naar rechts.

Bijvoorbeeld, het getal 121 tijdens het lezen van links naar rechts en van rechts naar links luidt hetzelfde, d.w.z. 121. 121 is dus een palindroom.

Het getal 291, wanneer van rechts naar links wordt gelezen, d.w.z. in omgekeerde volgorde, leest als 192. Daarom is 291 geen palindroom.

​

Uitgang:

Voer het nummer in om palindroom te controleren: 6556
Nummer 6556 is een palindroom

Screenshot voor hetzelfde wordt hieronder gegeven.

Recursie - Palindroom

In het bovenstaande programma lezen we het invoernummer uit de standaard invoer. Vervolgens geven we dit nummer door aan een recursieve functie om de cijfers van een nummer om te keren. Als de omgekeerde cijfers en het ingevoerde nummer hetzelfde zijn, is het nummer een palindroom.

Gevolgtrekking

Hiermee zijn we klaar met de recursie. In deze tutorial hebben we recursieve programmering, recursieve functie, de voor- en nadelen ervan, samen met verschillende voorbeelden in detail bestudeerd.

Afgezien van deze voorbeelden wordt recursie ook gebruikt bij het oplossen van enkele standaardproblemen zoals traversals (inorder / preorder / postorder), torens van Hanoi, BFS traversal, enz.

​ Bezoek hier om C ++ vanaf het begin te leren.

Aanbevolen literatuur

^