Programmeringskurs: 2.4 Rekursive algoritmer
Rekursjon
Det russiske leketøyet matrjosjka er en hul dukke som kan deles i to. Inne i hver dukke, er det en ny, mindre dukke. Når du åpner den første dukken, får du en ny dukke som er identisk, men mindre. Åpner du denne dukken, får du enda en mindre dukke. Og den kan du åpne igjen. Slik kan du fortsette å åpne helt til du når den minste, innerste dukken.
Den samme tankegangen gjelder for rekursive algoritmer. Da lager vi en oppskrift som bruker den samme oppskriften for å løse et problem. Hver gang vi skal løse problemet, må vi løse et nytt og mindre problem, helt til vi kommer til det minste problemet. Når vi har funnet den minste løsningen, kan vi steg for steg finne løsningene på de større problemene.
En rekursiv algoritme består av to deler
- Et rekursivt mønster for hvordan algoritmen kan bruke en mindre utgave av seg selv
- Et minste tilfelle som ikke kan beskrives av den samme algoritmen
a) Lag en rekursiv algoritme som regner ut #n!# (fakultet).
b) Test algoritmen på 5!
c) Implementer algoritmen i Python
Løsning
a) n! er definert som
#n! = \color{red}{n} \cdot (n-1) \cdot (n-2) \cdot \dots \cdot 3 \cdot 2 \cdot 1#
Når vi skal lage en rekursiv algoritme, må vi finne et mønster der oppskriften avhenger av en mindre utgave av seg selv. I tillegg må vi ha et minste tilfelle av algoritmen.
Vi ser at vi kan skrive
- Den rekursive delen er
#\quad n! = \color{red}{n} \cdot (n-1)!# - Den minste delen er
#\quad 1! = 1#
b) Vi følger gangen i algoritmen og bryter ned problemet i stadig mindre deler.
#5! = 5 \cdot 4!# #n! = n \cdot (n-1)!#
#4! = 4 \cdot 3!#
#3! = 3 \cdot 2!#
#2! = 2 \cdot 1!#
#1! = 1# Det minste tilfellet
Nå kan vi bygge oss opp igjen
#2! = 2 \cdot 1 = 2#
#3! = 3 \cdot 2 = 6#
#4! = 4 \cdot 6 = 24#
#5! = 5 \cdot 24 = \dunderline{120}#
c) Vi definerer en rekursiv fakultets-funksjon. Det vil si at den bruker seg selv i definisjonen. For at ikke algoritmen skal løpe evig, må vi definere det minste tilfellet med en if-setning.
|
||||||
Når vi skal kjøre koden for n = 5, kaller vi på funksjonen med fakultet(5).
