recursie

recursie is het proces van het definiëren van een probleem (of de oplossing van een probleem) in termen van (een eenvoudigere versie van) zichzelf.

bijvoorbeeld, we kunnen de operatie “find your way home” definiëren als:

1. Als u thuis bent, stop dan met bewegen.

2. Zet een stap richting home.

3. “find your way home”.

Hier is de oplossing om de weg naar huis te vinden twee stappen (drie stappen). Ten eerste gaan we niet naar huis als we al thuis zijn., Ten tweede doen we een zeer eenvoudige actie die onze situatie eenvoudiger maakt om op te lossen. Eindelijk doen we het hele algoritme opnieuw.

het bovenstaande voorbeeld wordt tail recursie genoemd. Dit is waar het allerlaatste statement het recursieve algoritme aanroept. Staart recursie kan direct worden vertaald in lussen.

Hoe zou je een recursief “algoritme” schrijven voor het vinden van Temple Square?

een ander voorbeeld van recursie is het vinden van de maximale waarde in een lijst met getallen. De maximale waarde in een lijst is ofwel het eerste nummer of de grootste van de resterende nummers., Hier is hoe we de pseudocode van het algoritme schrijven:

Delen van een recursief algoritme

alle recursieve algoritmen moeten het volgende hebben:

1. basisgeval (d.w.z. wanneer stoppen)

2. werk naar basisgeval

3. recursieve aanroep (d.w.z. onszelf aanroepen)

De “work toward base case” is waar we het probleem eenvoudiger maken (bijvoorbeeld, verdeel de lijst in twee delen, elk kleiner dan het origineel). De recursieve aanroep, is waar we hetzelfde algoritme gebruiken om een eenvoudigere versie van het probleem op te lossen., Het basisscenario is de oplossing voor het” eenvoudigste ” mogelijke probleem (bijvoorbeeld, het basisscenario in het probleem ‘vind het grootste getal in een lijst’ zou zijn als de lijst slechts één getal had… en als er per definitie maar één getal is, is het het grootste).

eenvoudig voorbeeld: drie getallen toevoegen

drie getallen toevoegen is gelijk aan het toevoegen van de eerste twee getallen, en dan deze twee getallen opnieuw toevoegen.

(merk op dat in Matlab een functie kan worden aangeroepen zonder alle argumenten. De nargin-functie vertelt de computer hoeveel waarden zijn opgegeven., Dus add_numbers (1) zou een nargin van 1 hebben; add_numbers(1,1) zou een nargin van 2 hebben; add_numbers(1,1,1) zou een nargin van 3 hebben.)

Identificeer de 3 delen van het recursieve algoritme:

alle recursieve algoritmen moeten de volgende drie fasen hebben:

waarom recursie werkt

In een recursief algoritme “onthoudt” de computer elke eerdere toestand van het probleem. Deze informatie wordt ” vastgehouden “door de computer op de” activeringsstack ” (d.w.z. binnen de werkruimte van elke functie).

elke functie heeft zijn eigen werkruimte PER aanroep van de functie.,

doolhof voorbeeld:

beschouw een rechthoekig raster van kamers, waarbij elke kamer al dan niet deuren heeft aan de noord -, zuid -, oost-en westzijde.

Hoe vind je de weg uit een doolhof? Hier is een mogelijk “algoritme” voor het vinden van het antwoord:

voor elke deur in de huidige kamer, als de deur leidt naar de uitgang, neem die deur.

De “truc” hier is natuurlijk, hoe weten we of de deur naar een kamer leidt die naar de uitgang leidt? Het antwoord is dat we dat niet doen, maar we kunnen de computer het voor ons laten uitzoeken.

Wat is het recursieve deel van het bovenstaande algoritme?, Het is de “deur leidt uit het doolhof”. Hoe weten we of een deur uit het doolhof leidt? Dat weten we omdat we in de volgende kamer (door de deur) dezelfde vraag stellen: hoe komen we uit het doolhof?

wat er gebeurt is dat de computer ” onthoudt “alle”wat ifs”. Wat als ik de eerste deur neem, wat als ik de tweede deur neem, wat als ik de volgende deur neem, enz. En voor elke mogelijke deur waar je doorheen kunt, onthoudt de computer wat als is, en voor elke deur daarna, en daarna, enz., totdat het einde is gevonden.

Hier is een bijna daadwerkelijke code implementatie.,

vraag: Wat is het basisgeval hierboven?

antwoord: (dat was een strikvraag) er is geen basisgeval in de code. Je moet bij het begin controleren of de kamer de uitgang is. Als dat zo is, geen recursie!

  function success = find_way_out( maze, room ) if room is exit → return true room ← mark as visited % rest of code ... end  

vraag: hoe markeer je de kamer als bezocht?

antwoord: er zijn verschillende technieken. Als de kamer een structuur (of object) is, kunt u de bezochte veldrichting aan de kamer toevoegen. (bijv., kamer.bezocht = true;) Als u geen objecten gebruikt, kunt u een matrix van Booleaanse vlaggen hebben die dezelfde grootte/vorm heeft als het doolhof en deze waarden gebruiken.,

Vraag: zijn de andere problemen met het bovenstaande algoritme?

antwoord: het antwoord hierop kan worden gevonden door na te denken over de volgende vraag: Wat zou er gebeuren als het doolhof een gigantisch raster zou zijn van identieke rechthoekige kamers, elk met deuren op elke muur? Stel je voor dat je naar het noorden gaat door de eerste deur, dan naar het oosten door de volgende kamerdeur, dan naar het zuiden door die kamerdeur, en dan naar het westen door die kamerdeur. Waar eindig je? Terug naar waar je begon! Erger nog, je zou deze lus voor altijd kunnen blijven maken. Hoe zou een onverschrokken avonturier dit probleem oplossen?,

een antwoord hierop is door een stuk krijt te gebruiken en een grote X op de vloer van elke kamer te plaatsen die je binnenkomt. Dus als je terug komt naar een kamer met een X op de vloer, Weet je dat je niet naar binnen hoeft te gaan. In het geval van het programma moet een Booleaanse vlag “gezien” of “bezocht” worden gebruikt. Elke kamer heeft een vlag. Elke kamer begint met de vlag wordt ingesteld op false. Als je een kamer bezoekt, zet je de vlag op true., Tot slot, in het” base case”heb je een regel als:

  function success = find_way_out( maze, room ) % exit chack if room is visited → return false % rest of code ... end  

recursie kan net zo goed worden toegepast op computeralgoritmen:

enkele computergerelateerde voorbeelden zijn: het toevoegen van een lijst met getallen, het berekenen van de Fibonacci-reeks, het berekenen van een faculteit en Sudoku.

Loops en Tail recursie

sommige recursieve algoritmen lijken erg op loops. Deze algoritmen worden ” staart recursief “genoemd omdat de laatste verklaring in het algoritme is om het algoritme” opnieuw op te starten”. Staart recursieve algoritmen kunnen direct worden vertaald in lussen.