Kapittel 7: Induksjon og rekursjon

Ductus, fra ducere, betyr å lede eller å trekke, på Latin. Induction i matematikk er en bevisform der sannheten av et utsagn for en verdi av en variabel trekker med seg sannheten av utsagnet for neste verdi av variabelen.

Cursor, fra currere, betyr noe/en som løper, på Latin. Recursion betyr derfor å løpe på nytt, dvs. å gjøre noe om (og om) igjen.

Tallfølger

Rekursjon er en metode for å definere en følge av matematiske objekter, ved hjelp av de matematiske objektene som allerede er definert.

For enkelhets skyld ser vi på tilfellet der disse matematiske objektene er reelle tall, dvs. vi vil definere en tallfølge.

Definisjon: En tallfølge er en ordnet liste av tall:

x1, x2, x3, ..., xn, xn+1, ...

For eksempel har vi listen av positive partall

2, 4, 6, ..., 2n, 2(n+1), ...

der xn = 2n for hver n ≥ 1. Et annet eksempel er listen av primtall

2, 3, 5, 7, 11, ..., pn, pn+1, ...

der pn er det n-te primtallet, for n ≥ 1. Vi skriver kort (xn)n for en slik tallfølge.

Følger som funksjoner

Vi kan også tenke på en tallfølge som en funksjon

f : N  R

fra mengden N av naturlige tall til mengden R av reelle tall. For gitt en tallfølge (xn)n kan vi definere en slik funksjon f ved f(n) = xn for hver n ≥ 1. Omvendt, gitt en slik funksjon f kan vi definere en tallfølge (xn)n ved samme formel: xn = f(n) for hver n ≥ 1. Vi kan derfor også skrive tallfølgen som følgen av funksjonsverdier for funksjonen f:

f(1), f(2), f(3), ..., f(n), f(n+1), ...

Hvis vi i stedet var interessert i følger av noen matematiske objekter som er elementer i en mengde A, så ville vi kunne se på dem som funksjoner

f : N  A

Dette kunne f.eks. være følger av bit-sekvenser, følger av logiske uttrykk eller følger av konfigurasjoner i et dynamisk system. Vi vil som sagt holde oss til tilfellet A = R.

Rekursive definisjoner

En tallfølge med n-te ledd f(n) kan noen ganger defineres slik som vi definerer funksjoner, enten ved en formel:

f(n) = 2n

eller ved en annen direkte beskrivelse: “f(n) er det n-te primtallet”. Slike definisjoner kalles ikke-rekursive.

Definisjon: En rekursiv definisjon av en tallfølge f(n) for n  N er en definisjon der beskrivelsen av det n-te leddet i følgen, f(n), er gitt ved hjelp av de foregående leddene f(1), f(2), ..., f(n-1) i følgen.

For n=1 sier dette bare at f(1) er definert på en eller annen måte. Vi kaller dette utgangspunktet for, eller starten på, den rekursive definisjonen. Så er f(2) definert ved hjelp av f(1), og deretter er f(3) definert ved hjelp av f(1) og f(2). Og så videre.

Enkle rekursjoner

For eksempel kan listen av partall f(n) = 2n defineres rekursivt ved å si at:

f(1) = 2

og

f(n) = f(n-1) + 2 for hver n  2

Da er funksjonsverdien f(n) ikke gitt ved en direkte formel, men gitt indirekte, ved hjelp av den (ene) foregående funksjonsverdien f(n-1). For å beregne f(2) bruker vi den tidligere verdien f(1) = 2, og formelen i tilfellet n=2: f(2) = f(1) + 2, så f(2) = 2 + 2 = 4. For å beregne f(3) bruker vi formelen for n=3: f(3) = f(2) + 2, og den foregående verdien f(2) = 4, så f(3) = 4 + 2 = 6. Og så videre.

Som dette eksempelet viser kan den samme tallfølgen ofte både gis en rekursiv og en ikke-rekursiv definisjon.

Dersom den rekursive definisjonen av det n-te leddet f(n) i en tallfølge bare er gitt ved hjelp av det umiddelbart foregående leddet f(n-1) i følgen, for n  2, så kan vi si at følgen er gitt ved enkel rekursjon (simple recursion).

Som et annet eksempel kan listen av primtall f(n) = pn også defineres rekursivt ved:

f(1) = 2

og

f(n) = det første tallet p man kommer til ved å begynne fra f(n-1) og legge	til 1 inntil man kommer til et tall uten faktorer mellom 1 og p,

for hver n  2.

Men dette er kanskje ikke en så effektiv rekursiv definisjon som det forrige eksempelet.

Fibonacci-følgen

Dette var to eksempler på enkle rekursive definisjoner. Et velkjent eksempel på en ikke-enkel rekursiv definisjon er Fibonacci-følgen F(n) for n  1, oppkalt etter Leonardo av Pisa. Starten på denne definisjonen gir de to første leddene,

F(1) og F(2), og deretter er F(n) definer ved hjelp av de to foregående leddene, for hver n  3.

Definisjon: Fibonacci-følgen (F(n))n er definert ved:

F(1) = 1

F(2) = 1

F(n) = F(n-2) + F(n-1) for hver n  3.

Da er F(3) = F(1) + F(2) = 1 + 1 = 2, ved formelen for n=3.

Så er F(4) = F(2) + F(3) = 1 + 2 = 3, ved formelen for n=4.

Videre er F(5) = F(3) + F(4) = 2 + 3 = 5, F(6) =F(4) + F(5) =3 + 5 = 8.

Og så videre. Denne tallfølgen begynner:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...

I Liber Abaci (1202) utledes denne definisjonen fra følgende problemstilling: Ett par kaniner (en hann og en hunn) plasseres på en øy. Hver måned etter at de er 2 måneder gamle avler hvert par et nytt par kaniner. Hvor mange kaninpar er det etter n måneder? Jo, det er F(n) par. For etter n måneder har vi de parene som var der måneden før, som det er F(n-1) av, pluss de nyfødte fra parene som er minst to måneder gamle, som det er F(n-2) av.

Iterative algoritmer

De m første partallene kan skrives ut av følgende ikke-rekursive algoritme:

1. Input m

2. For n = 1 to m do

2.1. f  2n

2.2. Output f

Alternativt kan vi bruke den rekursive definisjonen:

1. Input m

2. f  2

3. Output f

4. For n = 2 to m do

4.1. f  f + 2

4.2. Output f

Dette er en iterativ algoritme, fordi den i en for-løkke gjentatt beregner den nye verdien i tallfølgen ved hjelp av den foregående, men den er ikke en rekursiv algoritme, fordi den ikke inneholder en funksjon (prosedyre, metode) som kaller på en “annen kopi av seg selv”.

For Fibonacci-tallene kan vi også lage en iterativ algoritme:

1. Input m

2. gml  1

3. Output gml

4. ny  1

5. Output ny

6. For m = 3 to n do

6.1. sum  gml + ny

6.2. gml  ny

6.3. ny  sum

6.4. Output ny

Siden definisjonen av F(n) = sum involverer verdien av F(n-2) = gml og F(n-1) = ny, og den nye verdien i én iterasjon skal bli den gamle verdien i neste, så trenger vi tre variable for å holde styr på alle dataene. Dette er heller ikke en rekursiv algoritme.

2005-03-02T15:06:47