Nederlands
Menu

Wat is Recursie?

Een functie die zichzelf aanroept als onderdeel van haar eigen verwerking. Het probleem wordt opgesplitst in kleinere problemen van dezelfde vorm, en de aanroepen stoppen bij een geval dat niet verder wordt opgesplitst (het basisgeval). Elke aanroep gebruikt stackruimte, dus te diepe recursie laat de stack overlopen. Staartrecursie, waarbij de recursieve aanroep het laatste is wat de functie doet, kan worden omgezet in een lus.

Japanse benaming: 再帰

“Recursie” komt voor in 14 oefenvragen uit 8 onderwerpen, bijv. Datastructuren en algoritmen, Linker, loader en uitvoerbare formaten, Basis van programmeren (pseudocode traceren).

Vakgebied: Datastructuren en algoritmen

Nu oefenen: vragen over Recursie

Wat gebeurt er als men bij het schrijven van een recursieve functie die zichzelf aanroept in RISC-V vergeet ra op de stack op te slaan?

  1. Ara wordt door de binnenste aanroep overschreven en de buitenste functie kan niet meer correct naar de juiste aanroeper terugkeren
  2. BDe CPU slaat ra automatisch op, dus er treedt geen probleem op
  3. CHet rekenresultaat wordt verdubbeld, ongeacht de recursiediepte
Antwoord en toelichting tonen

Antwoord: A. ra wordt door de binnenste aanroep overschreven en de buitenste functie kan niet meer correct naar de juiste aanroeper terugkeren

De jal van een recursieve aanroep overschrijft ra met „de instructie na de aanroep binnen de functie zelf”. Als dat niet is opgeslagen, keert de buitenste functie bij ret niet terug naar de oorspronkelijke aanroeper maar in zichzelf, waardoor dezelfde plaats herhaaldelijk wordt doorlopen of een storing optreedt. Daarom is afgesproken dat een functie die andere functies aanroept in de prologue ra op de stack opslaat en in de epiloog terugzet.

Wat gebeurt er in het algemeen op Linux en dergelijke als recursie te diep wordt en de bovengrens van de stack wordt overschreden?

  1. AEr wordt een guard page aangeraakt waarvan de toegang is verboden en die voorbij de stack ligt, en het programma eindigt abnormaal
  2. BHet OS verplaatst de stack automatisch naar schijf en er kan onbeperkt diep worden gerecurseerd
  3. COude stackframes worden automatisch gewist en de berekening gaat correct verder
Antwoord en toelichting tonen

Antwoord: A. Er wordt een guard page aangeraakt waarvan de toegang is verboden en die voorbij de stack ligt, en het programma eindigt abnormaal

De stack heeft een bovengrens en daarachter ligt een guard page waarvan de toegang is verboden. Als de stack door te diepe recursie deze bereikt, treedt een page fault op en stopt het OS het programma (segmentation fault). Het voordeel van de guard page is dat kan worden gestopt voordat andere data worden beschadigd. Hetzelfde gebeurt als een grote array als lokale variabele wordt gebruikt, dus grote data worden veiliger op de heap geplaatst.

“Recursie” in de toelichting

Vragen met “Recursie” (14)

  1. Wat gebeurt er als men bij het schrijven van een recursieve functie die zichzelf aanroept in RISC-V vergeet ra op de stack op te slaan?
  2. Welk effect heeft het toepassen van tail call optimization op de laatste recursieve aanroep van de bovenstaande functie?
  3. Wat gebeurt er in het algemeen op Linux en dergelijke als recursie te diep wordt en de bovengrens van de stack wordt overschreden?
  4. In een ongerichte graaf zijn de buren van elke knoop A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. Diepte-eerst zoeken met recursie begint bij knoop A. De buren worden in de vermelde volgorde onderzocht, en zodra een nog niet bezochte knoop wordt gevonden, gaat de zoekactie daarheen. In welke volgorde worden de knopen bezocht?
  5. Een functie fib(n) voor Fibonaccigetallen is met recursie gedefinieerd als „als n kleiner dan of gelijk aan 1 is, geef n terug; geef anders fib(n−1) + fib(n−2) terug”. Hoe vaak wordt fib aangeroepen als fib(5) wordt aangeroepen, de eerste aanroep meegerekend?
  6. Welk geheugengebied wordt gewoonlijk gebruikt om bij het aanroepen van een subroutine (functie) tijdelijk onder meer het terugkeeradres op te slaan?
  7. Waar wordt tijdens uitvoering een in een C-functie gedeclareerde lokale variabele (automatische variabele) zonder static geplaatst?
  8. Welk voordeel is juist van de indeling waarin heap en stack van een proces in tegengestelde richting groeien met ertussen een breed vrij gebied?
  9. Waarop moet worden gelet met betrekking tot overmatig stackgebruik bij een kleine microcontroller zonder MMU?
  10. In een graaf waarvan de kanten geen gewicht hebben, wil je vanaf een startknoop het kleinste aantal kanten naar elke andere knoop bepalen. Welke combinatie van zoekmethode en datastructuur is geschikt?
  11. Een functie f(x, y) is gedefinieerd als „als y gelijk is aan 0, geef x terug; geef anders f(y, x mod y) terug”. Wat is de teruggegeven waarde van f(84, 36), en hoe vaak wordt f aangeroepen, de eerste aanroep meegerekend?
  12. ÷ staat voor deling; bij toekenning aan een variabele van het type integer (ook een argument) worden de cijfers achter de komma weggelaten. Hoe vaak wordt pow aangeroepen, de eerste aanroep meegerekend, als de volgende functie pow wordt aangeroepen als pow(2, 10)?
  13. Wat is de retourwaarde als de volgende functie fib wordt aangeroepen als fib(10)?
  14. int is 32 bits (maximum 2147483647). Wat is de grootste n waarvoor de bovenstaande functie fact(n) de faculteit van n correct en zonder overloop teruggeeft?

Verwante termen

Stack (stapelgeheugen) Variabele Argument Array Stackframe Heap Diepte-eerst zoeken (depth-first search) Breedte-eerst zoeken (breadth-first search) Stackpointer Retourwaarde (return value)

Naar de woordenlijst