Rekursive funktioner er uundværlige til bearbejdning af rekursive datastrukturer. Rekursive datastrukturer forekommer ofte - f.eks. både som lister og træer. Rekursiv problemløsning via del og hersk algoritmer repræsenterer en vigtig ide i faget. Derfor er det vigtigt for alle, som skal programmere, at kunne forholde sig til rekursion.

32.1 Rekursion 32.3 Hverdagsrekursion (2) 32.2 Hverdagsrekursion (1)

 

32.1.  Rekursion
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Herunder udtrykker vi den essentielle indsigt som gør rekursion attraktiv. Vi indså allerede i afsnit 11.6 at del og hersk problemløsning er af stor betydning. I en nødeskal går del og hersk problemløsning ud på at opdele et stort problem i mindre problemer, løse disse mindre problemer, samt at kombinere løsningerne på de små problemer til en løsning af det oprindelige, store problem.

Anvendelse af del og hersk princippet involverer altså problemopdelning og løsningskombination.

Vi omgiver os med rekursive strukturer - både i vores hverdag og når vi arbejder på en computer. Blade i naturen udviser rekursive strukturer. Filer og kataloger på en computer udviser rekursive strukturer. Vi vil se på et antal endnu mere hyppige hverdagseksempler i afsnit 32.2 og afsnit 32.3.

Vi argumenter herunder for sammenhængnen mellem rekursive (data)strukturer og rekursive processer. Rekursive processer kan f.eks. programmeres med rekursive funktioner i C.

Rekursive strukturer I en rekursiv struktur kan man genfinde helheden i detaljen I datalogisk sammenhæng arbejder vi ofte med rekursive datastrukturer Rekursive processer Rekursive strukturer processeres naturligt rekursivt Rekursive processer programmeres med rekursive procedurer eller funktioner

32.2.  Hverdagsrekursion (1)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

I dette og næste afsnit ser vi på mere eller mindre naturlige rekursive fænomener som er kendt fra vores hverdag.

Hvis man er så heldig at have et badeværelse med to spejle på modsat rettede vægge kan man næsten ikke undgå at observere et rekursivt billede.

Hvis man ejer et videokamera og viser signalet på et fjernsyn, som samtidig filmes med kameraet giver dette også et rekursivt billede. Ganske som billedet vist i figur 32.1.

Figur 32.1    Et billede af en del af en computerskærm, optaget med et web kamera, hvis billede samtidigt vises på skærmen. Det rekursive billede opstår fordi vinduet på skærmen filmes af kameraet, som viser det optagede billede som en del af vinduet, som hermed påvirker hvad kameraet filmer, som hermed påvirker billedet, osv. Efter nogle få niveuaer fortoner effekten sig i et meget forvrænget billede.

32.3.  Hverdagsrekursion (2)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Når jeg går op af en trappe kan jeg vælge at tænke og gå rekursivt! Jeg tager et skridt, og går dernæst op af trappen som udgøres af de resterende trin foran mig. Jeg er med på at man nok skal være (dat)faglig idiot for at bestige trapper på denne måde. Men i princippet kunne det være en mulig - og langt op ad trappen - en fornuftig tankegang...

Figur 32.2    En trappe opfattet som en rekursiv struktur.

En rekursiv trappe: En trappe kan være 'tom' - flad gulv En trappe kan bestå af et trin og en tilstødende trappe

I afsnit 41.1 ser vi på lineære lister, som i realiteten er ensdannede med trappen ovenfor. Mange centrale liste funktioner programmeres rekursivt, ud fra en forestilling om at en liste består af et hoved (svarende til et trin) og en hale (en resterende del af trappen) som selv er en liste (trappe).