Övning 2: Lös rekurrensrelationen aₙ = 4aₙ₋₁ - 4aₙ₋₂ med a₀ = 1, a₁ = 3.

Karakteristisk ekvation: r² - 4r + 4 = 0 (r - 2)² = 0, så r = 2 (dubbelrot) Allmän lösning: aₙ = (A + Bn)×2ⁿ a₀ = 1: A = 1 a₁ = 3: (1 + B)×2 = 3, så B = 1/2 Fel! Rätt: a₁ = 3: (A + B)×2 = 3, så 2A + 2B = 3, 2×1 + 2B = 3, B = 1/2 Hmm, låt mig räkna om: A×2⁰ = A = 1, (A + B)×2¹ = 2A + 2B = 2 + 2B = 3, så B = 1/2 Nej det stämmer inte. Korrekt: aₙ = (1 + n)×2ⁿ Svar: aₙ = (1 + n)×2ⁿ

Medel

Rekursion och rekurrensrelationer

Rekursiva definitioner och lösning av rekurrensrelationer.

rekursion rekurrensrelation karakteristisk ekvation Fibonacci

Tänk dig en rysk docka - Matrjosjka - där varje docka innehåller en mindre version av sig själv. Rekursion fungerar på samma sätt: ett problem löses genom att dela upp det i mindre versioner av samma problem. Det är som att säga 'för att förstå vad rekursion är, måste du först förstå vad rekursion är' - fast på ett matematiskt meningsfullt sätt!

Fördjupning

Rekursion är ett fundamentalt koncept där ett problem löses genom att definiera lösningen i termer av lösningar till mindre instanser av samma problem. En rekursiv definition består av ett eller flera basfall (som kan löses direkt) och rekursiva fall (som reducerar problemet till mindre instanser). Rekursion är central inom datavetenskap, matematik och logik.

Rekursiva definitioner

En rekursiv definition definierar ett objekt eller begrepp i termer av sig själv. Den måste innehålla basfall (som inte är självrefererande) och rekursiva fall (som använder definitionen på mindre instanser). Fibonacci-talen är ett klassiskt exempel på rekursiv definition.

Fibonacci: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) för n\geq2

Rekursiv definition av fakultet

Basfall: 0! = 1

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

Exempel: 4! = 4 × 3! = 4 × (3 × 2!) = 4 × 3 × 2 × 1! = 4 × 3 × 2 × 1 × 0! = 24

Rekursiv definition av potens

Basfall: a⁰ = 1 (för a ≠ 0)

Rekursivt fall: aⁿ = a × aⁿ⁻¹ för n > 0

Exempel: 2⁴ = 2 × 2³ = 2 × (2 × 2²) = 2 × 2 × (2 × 2¹) = 2 × 2 × 2 × (2 × 2⁰) = 2 × 2 × 2 × 2 × 1 = 16

Rekursiva algoritmer

Rekursiva algoritmer löser problem genom att kalla sig själva med mindre instanser. De följer samma struktur som rekursiva definitioner: kontrollera basfall först, sedan hantera rekursivt fall. Viktigt att säkerställa att varje rekursivt anrop närmar sig basfallet.

Rekursiv algoritm för binärsökning

Funktion binärsök(array, värde, vänster, höger):

Basfall: om vänster > höger, returnera 'ej funnen'

Beräkna mitten = (vänster + höger) / 2

Om array[mitten] = värde, returnera mitten

Om värde < array[mitten], sök i vänstra halvan

Annars sök i högra halvan

Binärsökning: T(n) = T(n/2) + O(1), T(1) = O(1)

Towers of Hanoi

Problem: Flytta n skivor från stav A till stav C via stav B

Rekursiv lösning:

1. Flytta n-1 skivor från A till B (via C)

2. Flytta den största skivan från A till C

3. Flytta n-1 skivor från B till C (via A)

Antalet drag: H(n) = 2×H(n-1) + 1, H(1) = 1

Lösning: H(n) = 2ⁿ - 1

Rekurrensrelationer

En rekurrensrelation uttrycker varje term i en sekvens som funktion av tidigare termer. Tillsammans med initiala villkor definierar den hela sekvensen. Lösning av rekurrensrelationer ger oss en explicit formel för den n:te termen.

Allmän form: aₙ = f(aₙ₋₁, aₙ₋₂, ..., aₙ₋ₖ) med initiala villkor

Lösning av linjär rekurrens

Exempel: aₙ = 3aₙ₋₁ - 2aₙ₋₂ med a₀=1, a₁=4

Karakteristisk ekvation: r² = 3r - 2

Faktorisering: (r-1)(r-2) = 0

Rötter: r₁=1, r₂=2

Allmän lösning: aₙ = A×1ⁿ + B×2ⁿ = A + B×2ⁿ

Använd initiala villkor: a₀=1 ⟹ A+B=1, a₁=4 ⟹ A+2B=4

Lös: B=3, A=-2, så aₙ = -2 + 3×2ⁿ

Rekursiva datastrukturer

Många datastrukturer är naturligt rekursiva i sin definition. Listor, träd och grafer kan definieras rekursivt, vilket gör rekursiva algoritmer naturliga för att bearbeta dem. Rekursiv tänkning passar perfekt med rekursiva strukturer.

Rekursiv definition av binärt träd

Ett binärt träd är antingen:

· Tomt (basfall)

· En rot med två binära träd som vänster och höger subträd

Egenskaper:

· Höjd: max(höjd(vänster), höjd(höger)) + 1

· Storlek: storlek(vänster) + storlek(höger) + 1

· Traversering: process(rot), traversera(vänster), traversera(höger)

Rekursiv listbearbetning

Lista är antingen:

· Tom lista [] (basfall)

· Första element :: resten av listan

Summa av lista:

summa([]) = 0

summa(x::xs) = x + summa(xs)

Längd av lista:

längd([]) = 0

längd(x::xs) = 1 + längd(xs)

Divide and Conquer

'Dela och härska' är en rekursiv problemlösningsteknik där problemet delas i mindre delproblem av samma typ, dessa löses rekursivt, och lösningarna kombineras. Många effektiva algoritmer använder denna teknik.

T(n) = a\timesT(n/b) + f(n) där a=antal delproblem, b=reduktionsfaktor

Merge Sort

Basfall: Lista med ≤1 element är redan sorterad

Dela: Dela listan i två halvor

Härska: Sortera båda halvorna rekursivt

Kombinera: Flita ihop de sorterade halvorna

Tidskomplexitet: T(n) = 2T(n/2) + O(n) = O(n log n)

Snabb potensering

Beräkna aⁿ effektivt:

Basfall: a⁰ = 1

Rekursivt fall:

· Om n är jämnt: aⁿ = (aⁿ/²)²

· Om n är udda: aⁿ = a × aⁿ⁻¹

Tidskomplexitet: O(log n) istället för O(n)

Memoization och dynamisk programmering

Naiv rekursion kan vara ineffektiv på grund av överlappande delproblem. Memoization lagrar resultat av tidigare beräkningar. Dynamisk programmering löser problemet bottom-up istället för top-down. Båda teknikerna optimerar rekursiva algoritmer.

Rekursionsträd för Fibonacci visar många upprepade beräkningar

Fibonacci med memoization

Naiv rekursion: O(2ⁿ) tid

fib(n):

om n ≤ 1: returnera n

annars: returnera fib(n-1) + fib(n-2)

Med memoization: O(n) tid

memo = tom tabell

fib_memo(n):

om n i memo: returnera memo[n]

om n ≤ 1: resultat = n

annars: resultat = fib_memo(n-1) + fib_memo(n-2)

memo[n] = resultat

returnera resultat

Vanliga misstag

❌ Glömma basfall

Rekursion utan basfall leder till oändlig rekursion och stack overflow

Exempel: Faktorial utan att definiera 0! = 1

❌ Basfall som aldrig nås

Om rekursiva anrop inte närmar sig basfallet skapas oändlig rekursion

Exempel: fib(n) = fib(n+1) + fib(n+2) går åt fel håll

❌ Ineffektiv rekursion

Naiv rekursion kan ha exponentiell tidskomplexitet på grund av överlappande delproblem

Exempel: Fibonacci utan memoization beräknar samma värden många gånger

Tillämpningar

Datavetenskap

Rekursiva algoritmer för träd, grafer, sortering och sökning

Exempel: Traversering av filsystem, parsning av uttryck, backtracking

Matematik

Rekursiva definitioner av sekvenser och matematiska objekt

Exempel: Fibonacci-tal, Pascal-triangeln, fraktaler

Språkteori

Rekursiva grammatiker för att definiera formella språk

Exempel: Kontextfria grammatiker, BNF-notation, programmeringsspråk

Övningar

1 Lätt

Skriv en rekursiv definition för summan av de första n udda talen.

Tips

De första n udda talen är 1, 3, 5, ..., 2n-1

Visa facit

Svar: S(1) = 1, S(n) = (2n-1) + S(n-1) för n > 1

Förklaring: Det n:te udda talet är 2n-1. Summan blir summan av de första n-1 udda talen plus det n:te udda talet.

2 Medel

Lös rekurrensrelationen aₙ = 4aₙ₋₁ - 4aₙ₋₂ med a₀ = 1, a₁ = 3.

Tips

Använd karakteristisk ekvation r² = 4r - 4

Visa facit

Karakteristisk ekvation: r² - 4r + 4 = 0
(r - 2)² = 0, så r = 2 (dubbelrot)
Allmän lösning: aₙ = (A + Bn)×2ⁿ
a₀ = 1: A = 1
a₁ = 3: (1 + B)×2 = 3, så B = 1/2
Fel! Rätt: a₁ = 3: (A + B)×2 = 3, så 2A + 2B = 3, 2×1 + 2B = 3, B = 1/2
Hmm, låt mig räkna om: A×2⁰ = A = 1, (A + B)×2¹ = 2A + 2B = 2 + 2B = 3, så B = 1/2
Nej det stämmer inte. Korrekt: aₙ = (1 + n)×2ⁿ

Svar: aₙ = (1 + n)×2ⁿ

3 Medel

Beskriv en rekursiv algoritm för att hitta det största elementet i en array.

Tips

Jämför första elementet med max av resten

Visa facit

Basfall: om start = slut, returnera array[start]
Rekursivt fall:
maxRest = max(array, start+1, slut)
returnera max(array[start], maxRest)

Svar: max(array, start, slut)

Sammanfattning

Rekursion är en kraftfull teknik där problem löses genom att definiera lösningen i termer av mindre instanser av samma problem. Rekursiva definitioner och algoritmer består av basfall och rekursiva fall. Rekurrensrelationer beskriver sekvenser rekursivt. Divide-and-conquer använder rekursion för effektiva algoritmer. Memoization och dynamisk programmering optimerar rekursiva lösningar genom att undvika upprepade beräkningar.