Övning 1: Definiera Fibonacci-tal rekursivt och beräkna F(5)

Definition: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) för n ≥ 2 F(2) = F(1) + F(0) = 1 + 0 = 1 F(3) = F(2) + F(1) = 1 + 1 = 2 F(4) = F(3) + F(2) = 2 + 1 = 3 F(5) = F(4) + F(3) = 3 + 2 = 5 Svar: F(5) = 5

Medel

Rekursion och definition

Rekursiva definitioner och strukturell induktion.

rekursion rekursiv definition strukturell induktion basfall

Har du någonsin tittat i en spegel som speglar sig i en annan spegel? Du ser en oändlig rad av reflektioner - varje reflektion skapar en ny, mindre version av sig själv. Detta är essensen av rekursion: något som definieras i termer av sig själv. I matematik och datavetenskap är rekursion ett kraftfullt verktyg för att definiera komplexa strukturer och lösa problem genom att bryta ner dem i mindre, likartade delar.

Fördjupning

Rekursiva definitioner definierar objekt eller funktioner i termer av sig själva, med basfall som stoppar rekursionen. Strukturell rekursion följer strukturen hos rekursivt definierade objekt som träd eller listor. Välgrundade rekursioner garanterar terminering genom att varje rekursivt anrop arbetar med 'mindre' input enligt någon välordnad relation. Rekursion är fundamental för definitioner av naturliga tal, datastrukturer och algoritmer.

Rekursiva definitioner - grundprinciper

En rekursiv definition består av två delar: basfall (som ger konkreta värden) och rekursiva fall (som refererar till definitionen själv).

Definition av naturliga tal

Basfall: 0 är ett naturligt tal

Rekursivt fall: Om n är ett naturligt tal, så är n+1 också ett naturligt tal

Inget annat är ett naturligt tal

Detta ger oss 0, 1, 2, 3, ... på ett präcist sätt

Fakultet - klassiskt exempel

Definition av n!:

· Basfall: 0! = 1

· Rekursivt fall: n! = n × (n-1)! för n > 0

Utföring:

4! = 4 × 3! = 4 × 3 × 2! = 4 × 3 × 2 × 1! = 4 × 3 × 2 × 1 × 0! = 4 × 3 × 2 × 1 × 1 = 24

Visuell representation av hur rekursiva definitioner byggs upp från basfall

Strukturell rekursion

Strukturell rekursion följer strukturen hos rekursivt definierade objekt som listor, träd eller logiska formler.

Rekursiva datastrukturer - binära träd

Basfall: Det tomma trädet (∅) är ett binärt träd

Rekursivt fall: Om L och R är binära träd och v är ett värde,

så är Node(v, L, R) ett binärt träd

Exempel: Node(5, Node(3, ∅, ∅), Node(7, ∅, ∅))

Höjd av binärt träd

Definition av height(T):

· Basfall: height(∅) = 0

· Rekursivt fall: height(Node(v, L, R)) = 1 + max(height(L), height(R))

Detta följer trädets struktur - höjden av ett träd är 1 plus höjden av det högsta subträdet.

Exempel på strukturell rekursion för träd och listor

Strukturell induktion

Strukturell induktion är bevismetoden för egenskaper hos rekursivt definierade strukturer. Den följer samma mönster som strukturens definition.

Strukturell induktion för listor

Basfall: Bevisa egenskapen för den tomma listan []

Induktivt fall: Antag egenskapen gäller för lista L

Bevisa att egenskapen gäller för x::L (x tillagd först)

Slutsats: Egenskapen gäller för alla listor

Bevis: Listlängd efter sammanslagning

Bevisa: length(L1 ++ L2) = length(L1) + length(L2)

Basfall: L1 = []

length([] ++ L2) = length(L2) = 0 + length(L2) = length([]) + length(L2) ✓

Induktivt fall: L1 = x::L1'

Antag: length(L1' ++ L2) = length(L1') + length(L2)

Visa: length((x::L1') ++ L2) = length(x::L1') + length(L2)

length((x::L1') ++ L2) = length(x::(L1' ++ L2)) = 1 + length(L1' ++ L2)

= 1 + length(L1') + length(L2) = length(x::L1') + length(L2) ✓

Välgrundade rekursioner

För att garantera att rekursiva definitioner är meningsfulla måste vi säkerställa att rekursionen terminerar.

Välgrundade relationer

En relation < är välgrundad om det inte finns oändliga fallande kedjor

Exempel: < på naturliga tal är välgrundad

Motexempel: < på heltal är inte välgrundad (...-2<-1<0)

Rekursion terminerar om varje anrop minskar enligt välgrundad relation

Euclidean algorithm för GCD

gcd(a, b) där a ≥ b > 0:

· Basfall: gcd(a, 0) = a

· Rekursivt fall: gcd(a, b) = gcd(b, a mod b)

Terminering: a mod b < b, så det andra argumentet minskar strikt i varje steg.

Ömsesidigt rekursiva definitioner

Ibland definieras flera funktioner eller begrepp i termer av varandra - ömsesidig rekursion.

Jämn och udda tal

even(0) = true

even(n) = odd(n-1) för n > 0

odd(0) = false

odd(n) = even(n-1) för n > 0

Funktionerna definierar varandra ömsesidigt

Visuell representation av ömsesidigt rekursiva definitioner

Vanliga misstag

❌ Sakna basfall

Rekursiva definitioner utan basfall leder till oändlig rekursion

Exempel: Fel: f(n) = f(n-1) + f(n-2) utan att definiera f(0) och f(1)

❌ Felaktig terminering

Rekursiva anrop som inte närmar sig basfall

Exempel: Fel: f(n) = f(n+1) - kommer aldrig nå basfall för f(0)

❌ Förväxla rekursion med cirkulär definition

Äkta rekursion måste ha progress mot basfall

Exempel: Cirkulär: A definieras som B, B definieras som A (ingen progress)

Tillämpningar

Algoritmer

Många effektiva algoritmer använder rekursiv divide-and-conquer strategi

Exempel: Merge sort, quick sort, binär sökning - alla bryter ner problem rekursivt

Datastrukturer

Träd, listor och andra strukturer definieras naturligt rekursivt

Exempel: JSON-objekt: värden kan vara skalarer eller andra JSON-objekt

Formell semantik

Betydelsen av programmeringsspråk definieras rekursivt över syntaxträd

Exempel: Betydelsen av (e1 + e2) är summan av betydelserna av e1 och e2

Matematik

Många matematiska objekt har naturliga rekursiva definitioner

Exempel: Fibonacci-tal, Peano-axiom för naturliga tal, strukturell induktion

Övningar

1 Lätt

Definiera Fibonacci-tal rekursivt och beräkna F(5)

Tips

Fibonacci-tal har två basfall: F(0) och F(1), sedan är varje tal summan av de två föregående

Visa facit

Definition: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) för n ≥ 2
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5

Svar: F(5) = 5

2 Medel

Definiera rekursivt funktionen sum(L) som summerar alla element i en lista

Tips

Basfall: tom lista. Rekursivt fall: första elementet plus summan av resten

Visa facit

Basfall: sum([]) = 0 (summan av tom lista är 0)
Rekursivt fall: sum(x::xs) = x + sum(xs)
Exempel: sum([1,2,3]) = 1 + sum([2,3]) = 1 + 2 + sum([3])
= 1 + 2 + 3 + sum([]) = 1 + 2 + 3 + 0 = 6

Svar: sum([]) = 0, sum(x::xs) = x + sum(xs)

3 Svår

Bevisa med strukturell induktion att reverse(reverse(L)) = L för alla listor L

Tips

Du behöver ett lemma om reverse(L ++ [x]) = x :: reverse(L)

Visa facit

Lemma: reverse(L ++ [x]) = x :: reverse(L) (bevisa först)
Basfall: reverse(reverse([])) = reverse([]) = [] ✓
Induktivt fall: Antag reverse(reverse(L)) = L
Visa: reverse(reverse(x::L)) = x::L
reverse(x::L) = reverse(L) ++ [x]
reverse(reverse(x::L)) = reverse(reverse(L) ++ [x])
= x :: reverse(reverse(L)) = x :: L (med lemma och hypotes)

Svar: Beviset använder strukturell induktion och ett hjälplemma

Sammanfattning

Rekursiva definitioner definierar objekt i termer av sig själva med basfall som säkerställer terminering. Strukturell rekursion följer strukturen hos rekursivt definierade objekt som träd och listor. Strukturell induktion är bevismetoden för egenskaper hos sådana strukturer. Välgrundade rekursioner garanterar terminering genom att varje rekursivt anrop 'minskar' enligt en välordnad relation. Rekursion är fundamental för algoritmer, datastrukturer och formella definitioner inom matematik och datavetenskap.