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 $n$ . 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

$a_n = f(a_{n-1})$

Eksplisitt vs. rekursiv formel
Type	Eksempel
Eksplisitt	aₙ = 200 · 0,8ⁿ (gir aₙ direkte fra n)
Rekursiv	aₙ = 0,8 · aₙ₋₁, a₀ = 200 (bygger på forrige ledd)

Tips

En rekursiv formel trenger ALLTID en STARTVERDI ( $a_0$ eller $a_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 nedbrytning av et kjemisk stoff rekursivt

Et kjemisk stoff i en løsning brytes ned slik at $20\ \%$ forsvinner hver time. Konsentrasjonen starter på $200$ mg/L. Sett opp en rekursiv formel, og finn konsentrasjonen etter $5$ timer ved å følge fremgangsmåten steg for steg.

Løsning:

Startverdien er $C_0 = 200$ , og hver time beholdes $80\ \%$ (siden $20\ \%$ brytes ned), så den rekursive formelen er $C_n = 0{,}8 \cdot C_{n-1}$
følg fremgangsmåten steg for steg: $C_1 = 0{,}8 \cdot 200 = 160$
$C_2 = 0{,}8 \cdot 160 = 128$
$C_3 = 0{,}8 \cdot 128 = 102{,}4$
$C_4 = 0{,}8 \cdot 102{,}4 = 81{,}92$
$C_5 = 0{,}8 \cdot 81{,}92 = 65{,}536$ . Etter $5$ timer er konsentrasjonen $\approx 65{,}5$ mg/L.

Fremgangsmåte (algoritme)
Steg	Handling	Resultat
1	Start: C = 200	200
2	Gjenta 5 ganger: C = 0,8 · C	…
3	Etter 5 gjentakelser	≈65,5

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 konsentrasjonen multipliseres med samme faktor hver time, kan den rekursive sammenhengen skrives om til en eksplisitt (geometrisk) formel: $C_n = 200 \cdot 0{,}8^n$ . Sett direkte inn $n = 5$ : $C_5 = 200 \cdot 0{,}8^5 \approx 200 \cdot 0{,}328 \approx 65{,}5$ : 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
Metode	C₅
Rekursiv (5 gjentakelser)	65,536
Eksplisitt (200 · 0,8⁵)	≈65,5 – 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

Uten et utgangspunkt kan ingen ledd regnes ut
en startverdi er nødvendig

Rekursiv formel
Krav	Betydning
Rekursiv formel	Trenger en startverdi

L-22En rekursiv formel er $a_n = a_{n-1} + 5$ , med $a_0 = 10$ . Hva er $a_1$ ?

Vis fasit

a0=10
a1 = 10 + 5 = 15

Finn a1
a0	Regel	a1
10	+5	15

L-23Hva kalles en formel som gir

a_n

direkte fra

n

, uten å bruke forrige ledd?

Vis fasit

En slik formel uttrykker a_n direkte via n, uten $a_{n-1}$
en eksplisitt formel

Type formel
Type	Kjennetegn
Eksplisitt	Gir aₙ direkte fra n

Middels(3)

M-21En rekursiv formel er $a_n = 0{,}9 \cdot a_{n-1}$ , med $a_0 = 500$ . Finn $a_1$ , $a_2$ og $a_3$ .

Vis fasit

a0=500
a1= $0{,}9 \cdot 500$ =450
a2= $0{,}9 \cdot 450$ =405
a3= $0{,}9 \cdot 405$ =364,5

Finn de neste leddene
Ledd	Verdi
a0	500
a1	450
a2	405
a3	364,5

M-22En radioaktiv kilde mister $10\ \%$ av massen sin hvert år, og starter på $500$ g. Hva er den rekursive formelen?

Vis fasit

Start 500, mister 10% hvert år (beholder 90%)
Mₙ = 0,9 · Mₙ₋₁, M₀ = 500

Sett opp den rekursive formelen
Del	Verdi
Beholder	90 %
Startverdi M₀	500 g

M-23En radioaktiv kilde mister $10\ \%$ av massen sin hvert år, og starter på $500$ g. Den rekursive formelen er $M_n = 0{,}9 \cdot M_{n-1}$ med $M_0 = 500$ . Finn massen etter $3$ år. Svar i g.

Vis fasit

Bruker rekursjonen 3 ganger, fra M0 til M3
M0=500
M1=450
M2=405
M3=364,5 g

Finn massen etter 3 år
År	Masse
0	500
1	450
2	405
3	364,5 g

Vanskelig(3)

V-21En dyrebestand følger

B_n = 1{,}02 \cdot B_{n-1} + 50

, med

B_0 = 1\ 000

(2 % vekst pluss et fast tilskudd fra innvandring hvert år). Finn

B_1

B_2

Vis fasit

B0=1 000
B1 = $1{,}02 \cdot 1\,000 + 50 = 1\,070$
B2 = $1{,}02 \cdot 1\,070 + 50$ ≈ 1 141,4

Finn B1 og B2
n	Bn
0	1 000
1	1 070
2	1 141,4

V-22En dyrebestand følger $B_n = 1{,}02 \cdot B_{n-1} + 50$ , med $B_0 = 1\ 000$ (2 % vekst pluss et fast tilskudd fra innvandring hvert år), og $B_1 = 1\ 070$ og $B_2 \approx 1\ 141{,}4$ . Fortsett rekken til $B_5$ . Svar avrundet til én desimal.

Vis fasit

Fortsetter fram til ledd 5, altså B5
B2≈1 141,4
B3≈1 214,2
B4≈1 288,5
B5 ≈ 1 364,3

Fortsett til B5
n	Bn
2	1 141,4
3	1 214,2
4	1 288,5
5	1 364,3

V-23Hvorfor er en bestandsmodell som

B_n = 1{,}02 \cdot B_{n-1} + 50

HVERKEN en ren aritmetisk ELLER en ren geometrisk rekke?

Vis fasit

Formelen har BÅDE en multiplikasjon (1,02·) OG en addisjon (+50)
kombinasjonen gjør den til en blandet, ikke ren, rekketype

Hvorfor verken ren aritmetisk eller geometrisk
Trekk	Type
1,02 · (multiplikasjon)	Geometrisk
+50 (addisjon)	Aritmetisk – kombinasjon av begge