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.

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

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.

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

Rekursiv formel
Krav	Betydning
Rekursiv formel	Trenger en startverdi

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

L-22En rekursiv formel er

a_n = a_{n-1} + 5

, med

a_0 = 10

. Hva er

a_1

Vis fasit

Finn a1
a0	Regel	a1
10	+5	15

a0=10
a1 = 10 + 5 = 15

L-23Hva kalles en formel som gir

a_n

direkte fra

n

, uten å bruke forrige ledd?

Vis fasit

Type formel
Type	Kjennetegn
Eksplisitt	Gir aₙ direkte fra n

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

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

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

a0=500
a1=0,9 gange 500=450
a2=0,9 gange 450=405
a3=0,9 gange 405=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

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

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

M-23Bruk formelen fra forrige oppgave til å finne massen etter

3

år.

Vis fasit

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

Bruker rekursjonen 3 ganger, fra M0 til M3
M0=500
M1=450
M2=405
M3=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

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

B0=1 000
B1 = 1,02 gange 1 000 + 50 = 1 070
B2 = 1,02 gange 1 070 + 50 ≈ 1 141,4

V-22Fortsett rekken fra forrige oppgave til

B_5

Vis fasit

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

Fortsetter fram til ledd 5, altså B5
B2≈1 141,4
B3≈1 214,2
B4≈1 288,5
B5 ≈ 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

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

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