0% fullført
Kapittel 11.3
I dette kapitlet skal du lære om rekursjon - når et ledd i en følge avhenger av de foregående leddene.
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.
an+1 = f(an)
Der neste ledd avhenger av forrige ledd
a₀ = [startverdi]
Vi må alltid ha en startverdi (første ledd)
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.
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, ...
Vi kan lage mange interessante følger ved å definere forskjellige funksjoner f(aₙ). La oss se på noen eksempler:
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, ...
En geometrisk følge er en spesiell type rekursiv følge der vi multipliserer med samme tall (kvotienten k) hver gang:
aₙ₊₁ = k · aₙ
a₀ = [startverdi]
Dette gir følgen: a₀, k·a₀, k²·a₀, k³·a₀, ...
Eller eksplisitt: aₙ = a₀ · kⁿ
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)ⁿ
✓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