Rekursion og induktion (færdig) Flashcards
Hvad er Fibonacci tal?
Et numerisk mønster – en række tal, hvor et tal findes ved at tilføje de to tal før det.
f.eks.
0, 1, 1, 2, 3, 5, 8, 13, 21
(fordi 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5 osv.)
Hvad betyder en rekursiv definition af en funktion?
En beregning af en funktion er rekursiv, hvis funktionen selv anvendes undervejs i beregningen.
Fibonaccitallene er et eksempel på det. da det samme tal bruges til at beregne det næste tal - hver af de følgende tal er summen er de tidligere tal.
Hvad betyder en rekursiv definition af en mængde?
Det betyder, at en mængde er defineret ved at anvende regler, der refererer til mængden selv.
Et eksempel på en rekursiv definition af en mængde er definitionen af de naturlige tal. De naturlige tal kan defineres som følger:
1 er et naturligt tal.
Hvis n er et naturligt tal, så er n+1 også et naturligt tal.
Således er alle naturlige tal defineret ved at anvende regler, der refererer til mængden selv, og derfor er det en rekursiv definition.
Hvad betyder en rekursiv definition på et træ?
Det kan for eksempel være en definition, hvor en node defineres som en samling af data og et antal undernoder, hvor hver undernode igen er en node i træet. På denne måde kan man konstruere et træ ved at starte med en rødder og derefter anvende reglerne for at definere hver undernode i træet.
Hvad er et binær træ?
Et binært træ kan være rekursivt defineret, da det ofte defineres ved hjælp af regler, der refererer til dets undernoder. En binær træ node er typisk defineret som en samling af data og to undernoder, hvor hver undernode er en node i træet.
Således kan man konstruere et binært træ ved at starte med en rødder og derefter anvende reglerne for at definere hver undernode i træet, hvilket gør det rekursivt defineret.
Binære træer bruges ofte i datalogi for at sortere og søge data effektivt.
Det kan f.eks. være beslutningstræer (evt. tal om vores projekt)
Hvad er en rekursiv algoritme?
Eksempel er MergeSort i workshop 3.
En algoritme som kalder sig selv.
