Nada

Grudat 2004-11-03

Föreläsning 3: Rekursion, binärträd

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.

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(2010) ge värdet 68. 

   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 68 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(2010) ger så småningom upphov till anropet age(2009). Då avbryts tillfälligt exekveringen av age(2010) och en kopia av age trollas fram och börjar exekvera. Kopian har en egen variabel year som sätts till 2009, allt medan original-ages year fortsätter att vara 2010. Så småningom har 68 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 sextionionde 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 68 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.
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

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 2010
Tekniskt stöd: <webmaster@nada.kth.se>