Introduktion till programmering, del 6- Funktionell programmering och rekursion

Ännu en onsdag, introduktionen fortsätter!

Förra veckan tittade vi på import av bibliotek och grundläggande GPIO på Raspberry Pi .

Som du kanske minns har vi kort nämnt Funktionell programmering i ett av de första avsnitten. Nu ska vi titta lite mer på det, och på samma gång lära oss olika sätt att lösa samma problem!

När man programmerar funktionellt försöker man alltid bryta ner problemen i små funktioner, och låter dessa samverka för att skapa en större helhet. Matematiska funktioner är en inspiration, men dessa är också relativt lätta att implementera. Här är ett exempel på den matematiska funktionen “fakultet”, skriven i Python:

def fak (x):
 svar = 1
 while x > 0:
  svar = x*svar
  x = x-1
 return svar

OBS! Använder ett enda mellanslag för indenteringen i denna kod, för TAB ville inte fungera här i blogginlägget. Därför är inte koden riktigt lika tydlig som vanligt.

Första raden sätter vi “svar” till 1, annars blir beräkningen i while-loopen (svar = x*svar) alltid 0, och det vill vi ju inte. Loopen körs sedan tills vi kommer ner till 0, och därefter returneras svaret. Det finns ett problem med den här koden. Kan du upptäcka vad? Svar finns i “spoiler”-rutan här nedan!

if x<1:
 return "Fel indata!"

Men finns det inget smidigare sätt att lösa den här funktionen på? Det är ju ändå rätt mycket kod för att lösa ett så simpelt problem?

Klart det finns! Vi ska nu titta på rekursion! 😉

Rekursion

Om du googlar på “recursion” och klickar på “Menade du: recursion” så kommer du förstå precis vad det här handlar om. Förenklat kan man säga att rekursion går ut på att en funktion återanropar sig själv. Det finns också två typer av rekursion, en där man ackumulerar resultatet under beräkningens gång, och en som först bygger den datamängd som ska beräknas, och därefter beräknar den. Vi börjar med samma funktion som ovan, som ackumulerande funktion:

def fak (x):
 if not isinstance(x, int) or x < 1:
  return "Felaktig input (heltal > 0)"
 else:
  return fakiter(x, 1)

def fakiter (x, acc):
 if x == 1:
  return acc
 else:
  return fakiter (x-1, acc*x)

Men, hallå! Det här blev ju inte mindre kod!

Nej, det är sant. Det är mer kod nu (eftersom det är två funktioner). Men hälften av koden är en stödfunktion som först kontrollerar invärdet (att det är ett heltal, och större än 0), och sedan anropar beräkningsfunktionen. “fakiter” är själva beräkningsfunktionen, men då den också har ett ackumulator-invärde kan man dölja detta för användaren med en “frontfunktion”, som jag har gjort.

Nu är ju Python smart på många sätt, så vi kunde lika gärna sätta ett standardvärde på acc=1 i fakiter(). Då hade vi kunnat skippa hjälpfunktionen, eller placera felkontrollen i samma funktion.

Så vad händer då i funktionen “fakiter”? Jo, först kontrolleras om det nuvarande talet är 1. I så fall avbryts beräkningen och resultatet, acc, returneras. Är x större anropar vi funktionen på nytt, men vi minskar x med 1 och multiplicerar vårt nuvarande resultat med x. Man kan alltså säga att anropen sker så här (användaren anropar bara “fak(3)”:

fak(3)
fakiter(3, 1)
fakiter(3-1, 1*3) -> fakiter(2, 3)
fakiter(2-1, 3*2) -> fakiter(1, 6)
x == 1, returnera 6

Smart, eller hur? Men nu ska vi titta på det andra sättet att beräkna rekursivt. Det är ännu häftigare!

Vi behåller vår hjälpfunktion, mest för att det är praktiskt att kontrollera invärden:

def fak (x):
 if not isinstance(x, int) or x < 1:
  return "Felaktig input (heltal > 0)"
 else:
  return fakrec(x)

def fakrec (x):
 if x == 1:
     return 1
 else:
  return x * fakrec(x-1)

Denna funktion ser hyfsat lika ut, eller hur? Beräkningen sker dock helt annorlunda. I den första varianten hade vi en ackumulator som samlade in vårt resultat, men här bygger vi upp beräkningen innan hela uttrycket beräknas. Ungefär så här kan man säga att exekveringen ser ut (återigen, endast fak(3) anropas av användare):

fak(3)
fakrec(3)
3 * fakrec(2)
3 * 2 * fakrec(1)
3 * 2 * 1
6

I det fallet x är 1 i den här funktionen returneras 1. Detta är eftersom vi sköter multiplikationen samtidigt som vi gör vårt rekursiva anrop (sista raden i fakrec), så vi vill avsluta med ett heltal.

En sak som också är bra att tänka på är att “return” alltid avslutar funktionen. Det betyder att “else:” i våra rekursiva funkioner är onödigt att skriva, eftersom return-anropet inuti if-satsen bara anropas när vi är färdiga med beräkningen.

Här är de båda funktionerna, utan “else:” och med standardvärde på acc:

def fakrec (x):
 if x == 1:
  return 1
 return x * fakrec(x-1)

def fakiter (x, acc=1):
 if x == 1:
  return acc
 return fakiter (x-1, acc*x)

Det var lite om rekursion, och allt för denna vecka!

Nästa vecka tar vi upp avancerade datatyper och objekt! Håll ut så länge 🙂

Uppdatering: Nästa avsnitt finns nu uppe!