Recursie is een fundamenteel concept in de informatica en wiskunde waarmee functies zichzelf kunnen aanroepen, waardoor complexe problemen via iteratieve stappen kunnen worden opgelost. Een visuele weergave die vaak wordt gebruikt om de uitvoering van recursieve functies te begrijpen en te analyseren, is een recursieboom. In dit artikel zullen we de theorie achter recursiebomen onderzoeken, hun structuur en hun betekenis voor het begrijpen van recursieve algoritmen.

Wat is een recursieboom?

Een recursieboom is een grafische weergave die de uitvoeringsstroom van een recursieve functie illustreert. Het biedt een visueel overzicht van recursieve oproepen, waarbij de voortgang van het algoritme wordt getoond terwijl het zich vertakt en uiteindelijk een basisscenario bereikt. De boomstructuur helpt bij het analyseren van de tijdscomplexiteit en het begrijpen van het betrokken recursieve proces.

string converteren naar int java

Boomstructuur

Elk knooppunt in een recursieboom vertegenwoordigt een bepaalde recursieve oproep. Het eerste gesprek wordt bovenaan weergegeven, met daaropvolgende gesprekken daaronder. De boom groeit naar beneden en vormt een hiërarchische structuur. De vertakkingsfactor van elk knooppunt hangt af van het aantal recursieve oproepen dat binnen de functie wordt gedaan. Bovendien komt de diepte van de boom overeen met het aantal recursieve oproepen voordat het basisscenario wordt bereikt.

Hoofdzaak

Het basisscenario dient als beëindigingsvoorwaarde voor een recursieve functie. Het definieert het punt waarop de recursie stopt en de functie waarden begint terug te geven. In een recursieboom worden de knooppunten die het basisscenario vertegenwoordigen gewoonlijk afgebeeld als bladknooppunten, omdat ze niet resulteren in verdere recursieve oproepen.

Recursieve oproepen

De onderliggende knooppunten in een recursieboom vertegenwoordigen de recursieve oproepen die binnen de functie worden gedaan. Elk kindknooppunt komt overeen met een afzonderlijke recursieve aanroep, wat resulteert in het creëren van nieuwe subproblemen. De waarden of parameters die aan deze recursieve oproepen worden doorgegeven, kunnen verschillen, wat leidt tot variaties in de kenmerken van de subproblemen.

Uitvoeringsstroom:

Het doorlopen van een recursieboom geeft inzicht in de uitvoeringsstroom van een recursieve functie. Vanaf de eerste oproep bij het hoofdknooppunt volgen we de vertakkingen om volgende oproepen te bereiken totdat we het basisscenario tegenkomen. Naarmate de basisgevallen worden bereikt, beginnen de recursieve oproepen terug te keren en worden hun respectieve knooppunten in de boom gemarkeerd met de geretourneerde waarden. Het traject gaat door totdat de hele boom is doorlopen.

Tijdcomplexiteitsanalyse

Recursiebomen helpen bij het analyseren van de tijdscomplexiteit van recursieve algoritmen. Door de structuur van de boom te onderzoeken, kunnen we het aantal recursieve oproepen en het werk op elk niveau bepalen. Deze analyse helpt bij het begrijpen van de algehele efficiëntie van het algoritme en het identificeren van eventuele inefficiënties of mogelijkheden voor optimalisatie.

Invoering

• Denk aan een programma dat de faculteit van een getal bepaalt. Deze functie neemt een getal N als invoer en retourneert als resultaat de faculteit van N. De pseudo-code van deze functie zal lijken op:

 // find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ 

• Recursie wordt geïllustreerd door de eerder genoemde functie. We roepen een functie aan om de faculteit van een getal te bepalen. Vervolgens roept deze functie zichzelf aan, gegeven een lagere waarde van hetzelfde getal. Dit gaat door totdat we het basisgeval bereiken, waarin er geen functieaanroepen meer zijn.
• Recursie is een techniek voor het omgaan met ingewikkelde problemen waarbij de uitkomst afhankelijk is van de uitkomsten van kleinere instanties van hetzelfde probleem.
• Als we aan functies denken, wordt een functie recursief genoemd als hij zichzelf blijft aanroepen totdat hij het basisscenario bereikt.
• Elke recursieve functie heeft twee hoofdcomponenten: het basisscenario en de recursieve stap. We gaan niet meer naar de recursieve fase zodra we het basisgeval hebben bereikt. Om eindeloze recursie te voorkomen, moeten basisgevallen goed worden gedefinieerd en zijn ze cruciaal. De definitie van oneindige recursie is een recursie die nooit het basisscenario bereikt. Als een programma nooit het basisscenario bereikt, zal er sprake blijven van stackoverflow.

Recursietypen

Over het algemeen zijn er twee verschillende vormen van recursie:

• Lineaire recursie
• Boomrecursie
• Lineaire recursie

Lineaire recursie

• Een functie die zichzelf elke keer dat deze wordt uitgevoerd slechts één keer aanroept, heet lineair recursief. Een mooie illustratie van lineaire recursie is de faculteitsfunctie. De naam 'lineaire recursie' verwijst naar het feit dat het uitvoeren van een lineair recursieve functie een lineaire hoeveelheid tijd kost.
• Bekijk de pseudo-code hieronder:

 function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } 

• Als we naar de functie doSomething(n) kijken, accepteert deze een parameter met de naam n en voert enkele berekeningen uit voordat dezelfde procedure nogmaals wordt aangeroepen, maar met lagere waarden.
• Wanneer de methode doSomething() wordt aangeroepen met de argumentwaarde n, stellen we dat T(n) de totale hoeveelheid tijd vertegenwoordigt die nodig is om de berekening te voltooien. Hiervoor kunnen we ook een herhalingsrelatie formuleren, T(n) = T(n-1) + K. K dient hier als constante. Constante K is opgenomen omdat het tijd kost voordat de functie geheugen aan een variabele toewijst of de toewijzing ervan ongedaan maakt, of een wiskundige bewerking uitvoert. We gebruiken K om de tijd te definiëren, omdat deze zo klein en onbeduidend is.
• De tijdscomplexiteit van dit recursieve programma kan eenvoudig worden berekend, aangezien in het ergste scenario de methode doSomething() n keer wordt aangeroepen. Formeel gesproken is de temporele complexiteit van de functie O(N).

Boomrecursie

• Wanneer u meer dan één keer een recursieve oproep doet in uw recursieve geval, wordt dit boomrecursie genoemd. Een effectieve illustratie van Tree-recursie is de fibonacci-reeks. Boom recursieve functies werken in exponentiële tijd; ze zijn niet lineair in hun temporele complexiteit.
• Kijk eens naar de pseudo-code hieronder,

 function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } 

• Het enige verschil tussen deze code en de vorige is dat deze nog één keer dezelfde functie aanroept met een lagere waarde van n.
• Laten we T(n) = T(n-1) + T(n-2) + k als de herhalingsrelatie voor deze functie nemen. K dient opnieuw als constante.
• Wanneer meer dan één aanroep naar dezelfde functie met kleinere waarden wordt uitgevoerd, staat dit soort recursie bekend als boomrecursie. Het intrigerende aspect is nu: hoe tijdrovend is deze functie?
• Doe een gok op basis van de onderstaande recursieboom voor dezelfde functie.
  
• Het kan bij u opkomen dat het een uitdaging is om de tijdscomplexiteit in te schatten door rechtstreeks naar een recursieve functie te kijken, vooral als het een boomrecursie is. Recursion Tree Method is een van de vele technieken voor het berekenen van de temporele complexiteit van dergelijke functies. Laten we het in meer detail onderzoeken.

Wat is de recursieboommethode?

• Recursierelaties zoals T(N) = T(N/2) + N of de twee die we eerder in de sectie over soorten recursie hebben besproken, worden opgelost met behulp van de recursieboombenadering. Deze terugkerende relaties maken vaak gebruik van een verdeel-en-heers-strategie om problemen aan te pakken.
• Het kost tijd om de antwoorden op de kleinere deelproblemen te integreren die ontstaan ​​wanneer een groter probleem wordt opgesplitst in kleinere deelproblemen.
• De herhalingsrelatie is bijvoorbeeld T(N) = 2 * T(N/2) + O(N) voor de samenvoegingssoort. De tijd die nodig is om de antwoorden op twee deelproblemen met een gecombineerde omvang van T(N/2) te combineren is O(N), wat ook geldt op implementatieniveau.
• Omdat de herhalingsrelatie voor binair zoeken bijvoorbeeld T(N) = T(N/2) + 1 is, weten we dat elke iteratie van binair zoeken resulteert in een zoekruimte die in tweeën wordt gesneden. Zodra de uitkomst is bepaald, verlaten we de functie. Aan de herhalingsrelatie is +1 toegevoegd omdat dit een constante-tijdbewerking is.
• De herhalingsrelatie T(n) = 2T(n/2) + Kn is er één om te overwegen. Kn geeft de hoeveelheid tijd aan die nodig is om de antwoorden op n/2-dimensionale subproblemen te combineren.
• Laten we de recursieboom voor de bovengenoemde herhalingsrelatie weergeven.

We kunnen een paar conclusies trekken uit het bestuderen van de bovenstaande recursieboom, waaronder

1. De omvang van het probleem op elk niveau is het enige dat telt voor het bepalen van de waarde van een knooppunt. De omvang van het probleem is n op niveau 0, n/2 op niveau 1, n/2 op niveau 2, enzovoort.

2. Over het algemeen definiëren we de hoogte van de boom als gelijk aan log (n), waarbij n de grootte van het probleem is, en de hoogte van deze recursieboom gelijk is aan het aantal niveaus in de boom. Dit is waar omdat, zoals we zojuist hebben vastgesteld, de verdeel-en-heers-strategie wordt gebruikt door herhalingsrelaties om problemen op te lossen, en om van probleemgrootte n naar probleemgrootte 1 te komen eenvoudigweg het nemen van log (n) stappen vereist.

• Neem bijvoorbeeld de waarde van N = 16. Als we N bij elke stap door 2 mogen delen, hoeveel stappen zijn er dan nodig om N = 1 te krijgen? Gezien het feit dat we bij elke stap door twee delen, is het juiste antwoord 4, wat de waarde is van log(16) met grondtal 2.

log(16) basis 2

vos of wolf

log(2^4) grondtal 2

4 * log(2) grondtal 2, aangezien log(a) grondtal a = 1

dus 4 * log(2) grondtal 2 = 4

3. Op elk niveau wordt de tweede term in de herhaling als root beschouwd.

Hoewel het woord 'boom' in de naam van deze strategie voorkomt, hoeft u geen expert op het gebied van bomen te zijn om het te begrijpen.

ex van gebruikersnaam

Hoe gebruik ik een recursieboom om herhalingsrelaties op te lossen?

De kosten van het subprobleem in de recursieboomtechniek zijn de hoeveelheid tijd die nodig is om het subprobleem op te lossen. Als u de uitdrukking 'kosten' opmerkt die verband houdt met de recursieboom, verwijst deze eenvoudigweg naar de hoeveelheid tijd die nodig is om een ​​bepaald deelprobleem op te lossen.

Laten we al deze stappen begrijpen met een paar voorbeelden.

Voorbeeld

Beschouw de herhalingsrelatie,

T(n) = 2T(n/2) + K

Oplossing

De gegeven herhalingsrelatie toont de volgende eigenschappen,

Een probleemgrootte n wordt verdeeld in twee deelproblemen van elk grootte n/2. De kosten voor het combineren van de oplossingen voor deze deelproblemen bedragen K.

Elke probleemgrootte van n/2 wordt verdeeld in twee subproblemen van elk grootte n/4 enzovoort.

Op het laatste niveau wordt de omvang van het subprobleem teruggebracht tot 1. Met andere woorden: we bereiken eindelijk het basisscenario.

converteer str naar int

Laten we de stappen volgen om deze herhalingsrelatie op te lossen,

Stap 1: Teken de recursieboom

Stap 2: Bereken de hoogte van de boom

Omdat we weten dat wanneer we een getal continu delen door 2, er een moment komt waarop dit getal wordt teruggebracht tot 1. Hetzelfde als bij de probleemgrootte N, stel dat na K-deling door 2 N gelijk wordt aan 1, wat impliceert: ( n / 2^k) = 1

Hier is n/2^k de probleemgrootte op het laatste niveau en deze is altijd gelijk aan 1.

Nu kunnen we eenvoudig de waarde van k berekenen uit de bovenstaande uitdrukking door log() naar beide kanten te nemen. Hieronder vindt u een duidelijkere afleiding,

n = 2 ^ k

• log(n) = log(2^k)
• log(n) = k * log(2)
• k = log(n) / log(2)
• k = log(n) grondtal 2

De hoogte van de boom is dus log (n) basis 2.

Stap 3: Bereken de kosten op elk niveau

css-lijsten

• Kosten op niveau 0 = K, twee subproblemen zijn samengevoegd.
• Kosten op niveau 1 = K + K = 2*K, twee deelproblemen worden twee keer samengevoegd.
• Kosten op niveau 2 = K + K + K + K = 4*K, twee deelproblemen worden vier keer samengevoegd. enzovoort....

Stap 4: Bereken het aantal knooppunten op elk niveau

Laten we eerst het aantal knooppunten op het laatste niveau bepalen. Uit de recursieboom kunnen we dit afleiden

• Niveau-0 heeft 1 (2^0) knooppunt
• Niveau-1 heeft 2 (2^1) knooppunten
• Niveau-2 heeft 4 (2^2) knooppunten
• Niveau-3 heeft 8 (2^3) knooppunten

Het niveau log(n) moet dus 2^(log(n)) knooppunten hebben, d.w.z. n knooppunten.

Stap 5: Tel de kosten van alle niveaus bij elkaar op

• De totale kosten kunnen worden geschreven als,
• Totale kosten = Kosten van alle niveaus behalve het laatste niveau + Kosten van het laatste niveau
• Totale kosten = Kosten voor niveau-0 + Kosten voor niveau-1 + Kosten voor niveau-2 +.... + Kosten voor niveau-log(n) + Kosten voor laatste niveau

De kosten van het laatste niveau worden afzonderlijk berekend omdat dit het basisscenario is en er op het laatste niveau geen samenvoeging plaatsvindt. De kosten voor het oplossen van een enkel probleem op dit niveau zijn dus een constante waarde. Laten we het nemen als O (1).

Laten we de waarden in de formules plaatsen,

• T(n) = K + 2*K + 4*K + .... + log(n)` keer + `O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n) keer)` + `O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) keer + O(n)

Als je de bovenstaande uitdrukking goed bekijkt, vormt deze een geometrische progressie (a, ar, ar^2, ar^3 ...... oneindige tijd). De som van GP wordt gegeven door S(N) = a / (r - 1). Hier is de eerste term en r is de gemeenschappelijke verhouding.