0% fullført
Kapittel 11.3
Rekursive følger
I dette kapitlet skal du lære om rekursjon - når et ledd i en følge avhenger av de foregående leddene.
Hva er rekursjon?
En rekursiv følge er en følge der hvert ledd defineres ut fra ett eller flere tidligere ledd. Dette kalles også en rekursiv definisjon.
Generell form
an+1 = f(an)
Der neste ledd avhenger av forrige ledd
a₀ = [startverdi]
Vi må alltid ha en startverdi (første ledd)
Fibonacci-følgen
Den berømte Fibonacci-følgen er kanskje det mest kjente eksemplet på en rekursiv følge. Hvert ledd er summen av de to foregående leddene.
Fibonacci-definisjonen
F₀ = 0
F₁ = 1
Fₙ = Fₙ₋₁ + Fₙ₋₂ (for n ≥ 2)
Dette gir følgen: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Generell form: aₙ₊₁ = f(aₙ)
Vi kan lage mange interessante følger ved å definere forskjellige funksjoner f(aₙ). La oss se på noen eksempler:
Eksempler på rekursive følger
aₙ₊₁ = 2·aₙ (geometrisk følge)
Med a₀ = 1: 1, 2, 4, 8, 16, ...
aₙ₊₁ = aₙ² (kvadratisk vekst)
Med a₀ = 2: 2, 4, 16, 256, ...
aₙ₊₁ = √aₙ (kvadratrot)
Med a₀ = 256: 256, 16, 4, 2, √2, ...
Geometrisk rekke
En geometrisk følge er en spesiell type rekursiv følge der vi multipliserer med samme tall (kvotienten k) hver gang:
Geometrisk følge
aₙ₊₁ = k · aₙ
a₀ = [startverdi]
Dette gir følgen: a₀, k·a₀, k²·a₀, k³·a₀, ...
Eller eksplisitt: aₙ = a₀ · kⁿ
Oppgaver
Følgen aₙ₊₁ = √(2 + aₙ) med a₀ = 0 konvergerer mot 2. Lag et program som:
Beregner de første 20 leddene
Viser hvor raskt følgen nærmer seg 2
Stopper når |aₙ - 2| < 0.0001
Du setter inn 10 000 kr på en konto med 4% årlig rente. Lag et program som bruker rekursjon til å:
Beregne din formue hvert år i 20 år
Finn hvilket år du passerer 20 000 kr
Sammenlign med den eksplisitte formelen: aₙ = 10000 · (1.04)ⁿ
Oppsummering
✓Rekursive følger defineres ved aₙ₊₁ = f(aₙ) med en startverdi a₀
✓Fibonacci-følgen: Fₙ = Fₙ₋₁ + Fₙ₋₂ med F₀ = 0, F₁ = 1
✓Geometrisk følge: aₙ₊₁ = k·aₙ gir aₙ = a₀·kⁿ
✓Sum av geometrisk rekke: Sₙ = a₀·(1 - kⁿ)/(1 - k)
✓Rekursive følger kan konvergere (nærme seg en verdi) eller divergere