Grudat 2004-11-03
Föreläsning 3: Rekursion, binärträd
- Rekursion
- Rekursiva dumsvar
- Rekursiva anrop
- Sifferexempel
- Listexempel
- Hur fungerar det?
- När fungerar det dåligt?
- Binärträd, introduktion
- Vetenskaplighet: Ockhams rakkniv
Rekursion
Rekursiv kommer från latinet och betyder återlöpande.
Definitioner kan vara rekursiva; till exempel kan man definiera
begreppet "avkomling" som "barn eller avkomling till barn". Men
rekursiva tankar kan också användas för problemlösning.
- Rekursiv tanke: reducerar problemet till ett enklare problem med samma struktur
- Basfall: det måste finnas ett fall som inte leder till rekursivt anrop
Rekursiva dumsvar
Nästa övning ägnas åt begreppet
rekursivt anrop, alltså när en metod anropar sej själv.
Det påminner om när man i vardagslivet besvarar en fråga på ett sätt
som framtvingar en liknande fråga som i sin tur besvaras på ett sätt
som framtvingar en liknande fråga etc. Exempel:
Fråga: Hur många år fyller du i år?
Rekursivt svar: Ett år mer än i fjol.
Om man ger sådana dumsvar blir man inte populär, men faktum är att
det går utmärkt att programmera på det sättet. Dock måste man se till
att rekursionen avslutas när man kommer ner till något enkelt
basfall. I mitt fall skulle jag behöva komplettera
dumsvaret så här:
...men år 1942 var jag noll år.
Med koden nedan skulle anropet age(2005)
ge värdet 63.
def age(year);
if year==1942: return 0
else: return 1+age(year-1)
Rekursiva anrop
Många undrar hur datorn gör när den får fram värdet 63 i exemplet ovan.
Egentligen ska man inte bekymra sej om det! Om den rekursiva tanken är
korrekt, så kommer datorn att räkna fram rätt värde. Men för den som envisas
med att vilja veta vad som händer kommer här den sanna beskrivningen.
Anropet age(2005)
ger så småningom upphov till anropet
age(2004)
. Då avbryts tillfälligt exekveringen av
age(2005)
och
en kopia av age
trollas fram och börjar exekvera. Kopian har
en egen variabel year
som sätts till 2004, allt medan
original-age
s year
fortsätter att vara 2005. Så småningom
har 63 olika age
anropats och alla är tillfälligt avbrutna i
väntan på att den anropade kopian ska komma tillbaka med ett siffervärde.
Och det sextiofjärde anropet, age(0)
returnerar verkligen genast
värdet 0. Då kan den sista age
slutföra beräkningen 1+0 och
returnera värdet 1, etc. Slutligen kan original-age
returnera
värdet 63 till huvudprogrammet, som inte har någon aning om hur mycket
arbete som skett bakom kulisserna!
Sifferexempel
Fråga: Hur många siffror har heltalet n?
Rekursivt svar: En siffra mer än om man stryker
sista siffran i n, ...men tal mindre än tio är ensiffriga.
def antalsiffror(n)
if n<10: return 1
return 1+antalsiffror(n/10)
Fråga: Vilken siffersumma har heltalet n?
Rekursivt svar: Sista siffran plus siffersumman om man stryker
sista siffran i n, ...men noll har siffersumman noll.
def siffersumma(n):
if n==0:
return 0
return (n%10) + siffersumma(n/10)
Fråga: Hur skriver man talet n binärt?
Rekursivt svar: Först skriver man n/2 binärt och sen
skriver man en nolla eller etta beroende på om n var jämnt eller udda,
...men talen 0 och 1 skrivs likadant binärt.
def writebinary(n):
if n==0 or n==1:
print n
else:
writebinary(n/2)
print n%2
Triangeltalet S(N) är summan av de N första heltalen. S(4)=1+2+3+4
Fråga: Vad är värdet på S(N)?
Rekursivt svar: S(N) = S(N-1) + N ... men S(1)=1.
Här följer en rekursiv metod för beräkning av triangeltalen:
def s(n):
if n==1: return 1
return s(n-1) + n
Listexempel
Vi tänker oss en länkad lista av objekt, där varje objekt innehåller
ett tal och en next-pekare. Variabeln top
pekar på den
översta posten.
Fråga: Hur många noder finns i stacken?
Rekursivt svar: En nod mer än i stacken under
topposten ...men en tom stack har noll poster.
def antal(p):
if p is None: return 0
return 1+antal(p.next)
Anropet antal(top)
ger nu rätt svar!
Hur fungerar det?
När man skriver egna rekursiva metoder bör man lita på att det rekursiva anropet
fungerar - man behöver inte analysera anropsgången för varje fall.
Men för att förstå varför rekursion kan vara extra minneskrävande är
det vara bra att känna till hur programspråken hanterar
rekursiva anrop.
- För varje anrop skapas en aktiveringspost som innehåller data
för anropet, t ex parametrar, lokala variabler och anropspunkt.
- Aktiveringsposten pushas på en stack.
- När det rekursiva anropet är klart poppas aktiveringsposten från stacken, varefter
föregående anrop ligger överst på stacken.
s(0) |
s(1) |
s(2) |
s(3) |
s(4) |
main() |
Aktiveringsposterna tar extra minne i anspråk och stackhanteringen tar extra tid,
så den extremt sparsamme skriver om sina rekursiva metoder. Vi andra nöjer oss med
kompilatorns optimeringar!
När fungerar det dåligt?
Det finns fall där en rekursiv lösning inte lämpar sig. Ett exempel är Fibonaccitalen.
Leonardo Fibonacci skrev år 1225 en bok där han beskrev denna intressanta talföljd:
Sista december föds en kaninpojke och en kaninflicka. Vid två månaders ålder
och varje månad därefter producerar varje kaninpar ett nytt kaninpar.
Månad |
0 (nov) |
1 (dec) |
2 (jan) |
3 (feb) |
4 (mar) |
5 (apr) |
6 (maj) |
7 (jun) |
8 (jul) |
9 (aug) |
Kaninpar |
0 |
1 |
1 |
2 |
3 |
5 |
8 |
13 |
21 |
34 |
def fib(n):
if n<=1: return n
return fib(n-1)+fib(n-2)
Man kan visa att antalet anrop faktiskt växer snabbare än själva Fibonaccitalen!
(För N=40 är Fibonaccitalet ca hundra miljoner men antalet rekursiva anrop är över 300 miljoner.)
Bättre vore här att använda en for-slinga:
def fib(n):
f0=0
f1=1
for i in range(n-1):
f2=f1+f0
f0=f1
f1=f2
return f1
Den här implementationen går i linjär tid, O(n).
Binärträd - introduktion
Ett binärträd är en länkad struktur med et värde och två pekare i varje nod.
class Node:
value=None
left=None
right=None
Utifrån når man trädet genom variabeln root
som pekar på
den översta noden (datalogiska träd har roten uppåt). Rotnodens
vänsterpekare pekar på ett mindre binärträd och högerpekaren på
ett annat mindre binärträd. Och det konstaterandet kan ses som en
rekursiv definition av begreppet binärträd!
Vad binärträd används till ska vi ta upp nästa vecka. Nu ska vi
se hur användbart det är med rekursiva tankar för binärträd.
Fråga: Hur många noder finns i binärträdet?
Rekursivt svar: En nod mer än i vänsterträdet och
högerträdet tillsammans ...men ett tomt träd har noll noder.
def antal(p):
if p is None: return 0
return 1+antal(p.left)+antal(p.right)
Anropet antal(root)
ger nu rätt svar!
Fråga: Hur skriver man ut hela binärträdet?
Rekursivt svar: Man skriver roten, sedan vänsterträdet och
sist högerträdet ...men ett tomt träd behöver man inte skriva ut.
def write(p):
if p is None: return
print p.value
write(p.left)
write(p.right)
Anropet write(root)
skriver ut hela trädet i en viss ordning
som kallas preordning. Genom att kasta om satserna får
man sex olika ordningar - alla användbara.
Några saker att minnas
- En rekursiv metod kan alltid omformuleras utan rekursion, men om det finns flera rekursiva anrop i metoden
kan det vara besvärligt.
- För många problem är en rekursiv metod mycket enklare att formulera och ger kortare kod än utan rekursion.
Ofta måste man gå via den rekursiva lösningen i tanken även om man gör en icke-rekursiv lösning.
- Den rekursiva metoden kräver i regel mer minne (och tar längre tid) än motsvarande icke-rekursiva metod.
Vetenskapliga principer: Ockhams rakkniv
Ockham var filosof år 1300, hans rakkniv är principen att välja den
enklaste teorin om det finns flera som kan förklara observationerna.
Exempel: När Newton kom med sin gravitationsteori fanns det redan en
teori som förklarade alla observationer. Man trodde att myriader av
osynliga änglar
transporterade alla fallande föremål. Men Ockhams rakkniv säger att
vi ska välja den enklare teorin som klarar sej med en enda ekvation.
Sidansvarig: <henrik@nada.kth.se>
Senast ändrad 7 november 2005
Tekniskt stöd: <webmaster@nada.kth.se>