Programmeren 13: Recursie

• Informatica
• Middelbare school
• havo, vwo
• Leerjaar 4-6

In deze video wordt Merge Sort uitgeplozen en wordt met een schema aangegeven wat er op de stack komt te staan en wanneer het er weer af gaat

https://youtu.be/GUGraK7dzYE

Deze afbeelding komt uit deze video van 28 min

Hele goede video met uitleg over recursie: https://www.youtube.com/watch?v=AfBqVVKg4GE&t=704s

Uitleg plaatje: Je praat over Alice, halverwege praat je verder over Bob, dan ga je verder met iets over Carol. Als dat klaar is maak je je verhaal over Bob af en kom je weer terug op je verhaal over Alice.

Overeenkomstig kun je functie-aanroepen weergeven.

Dit programma  (in de video in Python) staat in Flowgorithm: StackRecursie.fprg (Zie Domein D: grondslagen)

Opdracht 1:

Open Stack1.fprg en ga er stapsgewijs doorheen.

Je krijgt dezelfde Output.

Merk op hoe het programma door de verschillende functies, a, b en c, heengaat.

Eerst wordt de Output gegeven, dan wordt functie b aangeroepen. De rest van functie a wordt op de stack gezet.

Dit klassikaal doorlopen is ook prima en tegelijk op het bord tekenen

De stack bij dit programma ziet er als volgt uit:

Dit is nog geen recursie: Dan moet een functie zichzelf aanroepen

Opdracht 2:

Open het programma: Optellen2Getallen.fprg en run het stapsgewijs.

Teken een stack en teken hierin hoe de stack in dit programma gevuld en geleegd wordt

Opdracht 3:

Open het programma StackRecursie2.fprg en run het stapsgewijs.

1. Wat gaat hier niet goed en waarom?
2. Verander het programma zodanig, dat het op een gegeven moment eindigt. Schrijf in commentaar erbij wat je veranderd hebt en lever jouw versie in.

Open StackRecursie.fprg. Verander het programma zodanig dat dit de uitvoer wordt:

Sla het programma op en lever het in

Opdracht 4:

Open StackRecursie4.fprg en run het stapsgewijs.

Bepaal de uitvoer en teken de stack.

Let op: Als een commando op de stack gezet wordt, worden ook alle waarden van variabelen erop gezet oftewel opgeslagen, die op dat moment in gebruik zijn. Als het programma terugkeert naar dat commando, krijgen de variabelen weer de 'oude' waarde.

Hier volgen in dezelfde video 2 voorbeelden van recursie. Handig om te snappen, niet handig om zo toe te passen, maar dat maakt niet uit.

Factor (x) = Factor!

Fibonacci

Elke recursieve functie moet hebben:

• Een base case: De stop-conditie. Anders gaat hij oneindig door en krijg je een stack overflow
• een recursief statement: hierin roept de functie zichzelf aan, anders is het geen recursieve functie

Bekijk de 2 voorbeelden hiervan:

1. recursieFactorNOneindig
2. recursieFactorNEindig

Verander je Fibonacci-programma in een recursief programma. Zorg dat het begingetal niet te groot is. Maximaal 10.