Het basisgeval

Een script dat zichzelf bevat is recursief.

Het lijkt logisch om alle identieke genummerde boom-scripts te vervangen door een enkelvoudig recursief script met dezelfde structuur:
Geen Afbeelding  Geen Afbeelding       ...        Geen Afbeelding

Maar het werkte niet:
Geen Afbeelding

Bo: Aaarghhhh! Wat gaat er mis?!!!
Alex: Hij gaat maar door!
Yasmine: Nadat hij naar links draaide zou hij een kleinere boom moeten maken, maar dan zou hij moeten stoppen en naar rechts draaien en daar ook een boom maken.
Bo: Oh ja, Yasmine! Hij gaat niet naar rechts!
Yasmine: Yep, bij iedere recursieve aanroep naar boom tekent de sprite steeds kleinere takken totdat hij alleen maar rondjes lijkt te draaien. Hij tekent nooit een rechter tak om de boom af te maken waar hij mee bezig is.
Alex: Ik snap het. De oorspronkelijke genummerde blokken van boom 1, boom 2, enzovoort, zijn niet allemaal hetzelfde. De eerste, boom 1, is anders: hij tekent alleen een lijn zonder takken en zet de sprite terug waar hij begon.

Alex wijst naar de code van boom 1 en naar de figuur die daardoor getekend wordt.
Geen Afbeelding Geen Afbeelding

Bo: Dus ons blok voor de recursieve boom moet iets anders doen wanneer niveau = 1 !
Yasmine: Yep! Hij moet alleen maar een lijn tekenen zonder een andere tak toe te voegen.
Dit speciale geval voor het laagste niveau van een recursief programma heet het basisgeval.
Bo: Laten we eens met een eenvoudige boom nagaan om uit te zoeken hoe dit "basis geval" moet werken. Kijk eens naar boom 3met grootte 40.
Geen Afbeelding Geen Afbeelding
Alex: Oké, na het schoonvegen van het speelveld en naar boven richten en de pen neerzetten zet de sprite 40 stappen en draait daarna 25° naar links. En dan roept hij boom 2 aan met een kleinere grootte.
Bo: Goed. En boom 2 , die bijna hetzelfde is, beweegt, draait en roept dan boom 1 aan, die alleen maar een lijn tekent en terug gaat. Daarna moet de sprite van boom 2 60° naar rechts draaien en nog een kleine boom 1 te tekenen en….
Yasmine: Ja, en omdat boom 1 klaar is, wordt boom 2 beëindigd! Dus het ziet er zo uit als boom 2 klaar is:
Geen Afbeelding
Alex: Yep. En dan draait het script van boom 3 60° naar rechts en gebruikt weer het hele scripts van boom 2 om de andere kant te maken. Daarna draait hij 35° terug en beweegt achteruit naar het allereerste begin.
Geen Afbeelding
Bo: Dus zo eindigt boom 3. Over dat "basisgeval" voor het recursieve script… Het basis geval is het laagste niveau van de recursie, dus dat is zoals boom 1.
Alex: Yep, boom 1.
tekent alleen een lijn en gaat niet nog een boom maken.
Bo: Dus we moeten ons recursieve boom-blok een lijn laten tekenen op niveau 1 in plaats van eindeloos kleine bomen te maken.
  1. Corrigeer je recursieve boom-blok zodat het een basis geval bevat om te voorkomen dat het script zichzelf eindeloos aanroept. Hier geven we twee manieren om dat te doen, maar er zijn er meer. Gebruik de manier die voor jou het beste werkt.
    Geen Afbeelding               Geen Afbeelding
  2. Voer boom niveau: 9 en grootte: 50 uit. Als je dit correct doet, zou je dit moeten krijgen:
    Geen Afbeelding
  3. De tijdsduur om een boom te tekenen neemt heel snel toe met het aantal niveaus, dus we raden 20 niveaus af. Probeer maar eens de tijd voor niveau 8 tot en met 12 te meten.
  1. Analyseer: boom 1 maakt maar 1 stok. Hoeveel nieuwe stokken (takken) worden door boom 2 gemaakt? En hoeveel worden er door boom 3 gemaakt? Door boom 4? Achterhaal hoeveel nieuwe twijgen er worden toegevoegd op niveau 10. Je snapt nu waarom het zo lang duurt om niveau 20 te tekenen.
Geen Afbeelding

Recursieve scripts roepen zichtzelf aan. Om ze te laten stoppen moet er een speciaal geval zijn waarbij ze stoppen> met zichtzelf aanroepen. Dat wordt het basisgeval genoemd, een eenvoudigere versie van het script dat zichzelf niet aanroept .

Gewoonlijk is er een voorwaarde (zoals if-else) met 2 gevallen: een basisgeval voor het laagste niveau die voorkomt dat de recursie voor altijd doorgaat en een recursief geval dat het script steeds weer aanroept totdat het basis geval bereikt wordt.

Als een script zichzelf wel steeds recursief blijft aanroepen (zoals wanneer het script blijft ronddraaien op dezelfde plek), is dat een bug en dan zeggen we dat het programma vastzit in een oneindige lus.

  1. Voeg een globale variabele teller toe, die als eerste wordt verhoogd in het boomblok om het aantal keren te tellen dat boom wordt aangeroepen als er verschillende niveaus gerund worden. Maak een tabel. Welk patroon ontdek je?
    niveau teller
    1 1
    2 3
    3 7
    4 ?
    5  
    6  
    etc. etc.
    2. Dit is een voorbeeld van exponentiële groei. Deze soort groei in een algoritme neemt onredelijk veel tijd in beslag, zoals je zag in Hoofdstuk 5 les 3: Algoritmen classificeren. Dit is de reden waarom we adviseerden om niet 20 niveaus te proberen.
Terug Volgende