NumiSum

Rekursive sammenhenger og programmering

En REKURSIV formel definerer et ledd ut fra det/de FORRIGE leddet («neste = forrige pluss/ganger noe»), i motsetning til en EKSPLISITT formel som gir leddet direkte fra nn. Rekursive sammenhenger egner seg godt for PROGRAMMERING: en løkke som oppdaterer en verdi steg for steg, gjentatt like mange ganger som antall ledd du vil finne.

Rekursiv vekst

an=f(an−1)a_n = f(a_{n-1})

Eksplisitt vs. rekursiv formel
TypeEksempel
Eksplisittaₙ = 100 · 2ⁿ (gir aₙ direkte fra n)
Rekursivaₙ = 2 · aₙ₋₁, a₀ = 100 (bygger på forrige ledd)

Tips

  • En rekursiv formel trenger ALLTID en STARTVERDI (a0a_0 eller a1a_1) i tillegg til selve regelen – uten en startverdi kan du ikke regne ut noe som helst.
  • Skriv opp fremgangsmåten som en NUMMERERT liste med steg (start, oppdater, gjenta) – det er nettopp dette en programløkke gjør, bare med kode i stedet for ord.

Eksempel: Modellere en bakteriekultur rekursivt

En bakteriekultur starter med 100100 bakterier og dobler seg hver time. Sett opp en rekursiv formel, og finn antall bakterier etter 55 timer ved å følge fremgangsmåten steg for steg.

Fremgangsmåte (algoritme)
StegHandlingResultat
1Start: B = 100100
2Gjenta 5 ganger: B = 2 · B…
3Etter 5 gjentakelser3 200
Løsning:
  1. Startverdien er B0=100B_0 = 100, og hver time dobles antallet, så den rekursive formelen er Bn=2⋅Bn−1B_n = 2 \cdot B_{n-1}
  2. følg fremgangsmåten steg for steg: B1=2⋅100=200B_1 = 2 \cdot 100 = 200
  3. B2=2⋅200=400B_2 = 2 \cdot 200 = 400
  4. B3=2⋅400=800B_3 = 2 \cdot 400 = 800
  5. B4=2⋅800=1 600B_4 = 2 \cdot 800 = 1\ 600
  6. B5=2⋅1 600=3 200B_5 = 2 \cdot 1\ 600 = 3\ 200. Etter 55 timer er det 3 2003\ 200 bakterier.
Alternativ forklaring/metode: Finn den eksplisitte formelen i stedet for å gjenta steget

Alternativ metode – innenfor pensum, men ikke hovedmetoden her

Regne om til en eksplisitt formel

Siden bakteriekulturen dobles hver time, kan den rekursive sammenhengen skrives om til en eksplisitt (geometrisk) formel: Bn=100⋅2nB_n = 100 \cdot 2^n. Sett direkte inn n=5n = 5: B5=100⋅25=100⋅32=3 200B_5 = 100 \cdot 2^5 = 100 \cdot 32 = 3\ 200 – samme svar, men uten å måtte gjenta steget fem ganger. Eksplisitt formel er raskere for ETT enkelt ledd langt unna starten, mens den rekursive versjonen er mer naturlig å PROGRAMMERE som en løkke, og viser hele utviklingen underveis.

Rekursiv vs. eksplisitt
MetodeB₅
Rekursiv (5 gjentakelser)3 200
Eksplisitt (100 · 2⁵)3 200 – samme svar

Oppgaver

Prøv minst én oppgave på hvert nivå.

Lett(3)

L-21Hva trenger en rekursiv formel i tillegg til selve regelen?

Vis fasit
Rekursiv formel
KravBetydning
Rekursiv formelTrenger en startverdi
  1. Uten et utgangspunkt kan ingen ledd regnes ut
  2. en startverdi er nødvendig

L-22En rekursiv formel er an=an−1+5a_n = a_{n-1} + 5, med a0=10a_0 = 10. Hva er a1a_1?

Vis fasit
Finn a1
a0Regela1
10+515
  1. a0=10
  2. a1 = 10 + 5 = 15

L-23Hva kalles en formel som gir ana_n direkte fra nn, uten å bruke forrige ledd?

Vis fasit
Type formel
TypeKjennetegn
EksplisittGir aₙ direkte fra n
  1. En slik formel uttrykker a_n direkte via n, uten an−1a_{n-1}
  2. en eksplisitt formel
Middels(3)

M-21En rekursiv formel er an=3⋅an−1a_n = 3 \cdot a_{n-1}, med a0=2a_0 = 2. Finn a1a_1, a2a_2 og a3a_3.

Vis fasit
Finn de neste leddene
LeddVerdi
a02
a16
a218
a354
  1. a0=2
  2. a1=3 gange 2=6
  3. a2=3 gange 6=18
  4. a3=3 gange 18=54

M-22En bakteriekultur starter med 5050 bakterier og tredobles hver time. Hva er den rekursive formelen?

Vis fasit
Sett opp den rekursive formelen
DelVerdi
Vekstgange 3 hver time
Startverdi B₀50
  1. Start 50, tredobles hver time
  2. Bₙ = 3 · Bₙ₋₁, B₀ = 50

M-23Bruk formelen fra forrige oppgave til å finne antall bakterier etter 33 timer.

Vis fasit
Finn antall bakterier etter 3 timer
TimeBakterier
050
1150
2450
31 350
  1. Bruker rekursjonen 3 ganger, fra B0 til B3
  2. B0=50
  3. B1=150
  4. B2=450
  5. B3=1 350
Vanskelig(3)

V-21Et sparebeløp følger Kn=1,05⋅Kn−1+1 000K_n = 1,05 \cdot K_{n-1} + 1\ 000, med K0=0K_0 = 0 (rente pluss et fast innskudd hvert år). Finn K1K_1 og K2K_2.

Vis fasit
Finn K1 og K2
nKn
00
11 000 kr
22 050 kr
  1. K0=0
  2. K1 = 1,05 gange 0 + 1 000 = 1 000
  3. K2 = 1,05 gange 1 000 + 1 000 = 2 050 kr

V-22Fortsett rekken fra forrige oppgave til K5K_5.

Vis fasit
Fortsett til K5
nKn
22 050
33 152,5
44 310,13
55 526 kr
  1. Fortsetter fram til ledd 5, altså K5
  2. K2=2 050
  3. K3=3 152,5
  4. K4=4 310,13
  5. K5 ≈ 5 526 kr

V-23Hvorfor er en sparemodell som Kn=1,05⋅Kn−1+1 000K_n = 1,05 \cdot K_{n-1} + 1\ 000 HVERKEN en ren aritmetisk ELLER en ren geometrisk rekke?

Vis fasit
Hvorfor verken ren aritmetisk eller geometrisk
TrekkType
1,05 · (multiplikasjon)Geometrisk
+1 000 (addisjon)Aritmetisk – kombinasjon av begge
  1. Formelen har BÅDE en multiplikasjon (1,05·) OG en addisjon (+1 000)
  2. kombinasjonen gjør den til en blandet, ikke ren, rekketype