Rekursion för nybörjare

Vi har slutit fred, lispen och jag. När jag började plugga datateknik var det första programmeringsspråk vi fick använda ett s.k. funktionellt (jag vet att jag brukade säga dysfunktionellt) språk som hette Lisp. För mig som hade kodat lite C innan innebar Lisp en stor utmaning eftersom jag plötsligt skulle tänka på ett nytt sätt och glömma det jag kunde sedan tidigare. Jag minns att vår föreläsare visade mig min lösning (två sidor spaghettikod) på ett problem och sa att det där skulle säkert funka, men... det var ju inte Lisp. Han visade sedan en mer "lispig" lösning som bara tog upp några rader. Hemligheten är att lära sig använda rekursion på ett vettigt sätt. Jag lärde mig det där såpass att jag klarade kursen, men Lisp blev aldrig mitt favoritspråk... förrän nu. Nu när jag sitter och kodar Java som är mer modernt och populärt använder jag rekursion och andra gamla Lisp-knep och är väldigt glad över att jag fick lära mig det där. Stort tack till min lispföreläsare som jag hoppas kan glömma det där jag sa om att jag gillade C bättre (jag sa det, jag lovar). Jag har vuxit upp och kommit till insikt nu. :)

Rekursion för nybörjare! När man använder rekursion låter man ett program anropa sig själv. Tänk er att vi har programmet Godisräknaren. Den tar en godispåse som indata och ger antalet godisbitar som utdata. Den räknar godisar helt enkelt. :) Det luriga är ett en godispåse i detta fall kan innehålla nya påsar som i sin tur innehåller godisar eller ytterligare påsar. Hittas en godis så räknas den och adderas till resultatet, men hittas en ny påse så rekurserar vi! Vi skickar den nya påsen till räknaren och adderar slutresultatet från genomgången av den påsen till det antal godisar vi har hittat i den stora påsen. På så sätt går vi snabbt igenom alla påsarna utan att glömma någon. Vi behöver heller inte veta från början hur många påsar och godisar det rör sig om. Det där sköter rekursionen. Det blir väldigt lite kod och det går förhållandevis snabbt. (Dock får man en del myror i huvudet, men det går över.)

image185

Kommentarer
Postat av: Nostalgia for Infinity

ujuj, funktionella språk skrämmer mig. På LTH lärs enbart Haskell ut och det som frivillig kurs, så jag har inte fått bekanta mig med det men lite spännande låter det iaf :)
Men rekursion fick vi lära oss rätt så tidigt ändå, skäms lite över att jag inte kunde det innan. Kommer ihåg någonting om att "vadå, en funktion som anropar sig själv, va ska det va bra för?"...
iofs föredrar jag nog loopar ändå :)
Skall ju finnas en hemskhet om att det inte går att ha en oändlig rekursiv kedja för då får man slut på stackutrymme (lite skrämmande, men kanske ingenting som man orkar bry sig om i verkligheten?)

Postat av: Kaprifol

Ah, det verkar som att något funktionellt språk lärs ut på de flesta högskolor (eller att det iaf ges lite utbildning i hur rekursion går till). Visst är det läskigt, men oj så användbart ibland. Jodå, jag smashade sönder många stackar i unga år. ;)

2007-09-20 @ 18:57:12
URL: http://kaprifol.blogg.se
Postat av: Blaufish

Jag lärde mig länkade listor när jag var 15, långt innan jag lärde mig rekursion.
I något program fanns någon hemsk logik där allt gjordes i en serie while-snurror som sprang up och ner rekursivt. Precis som funktionsrekursion, bara det att jag hade lista istället, och manipulerade en parent pekare för att kunna rekursera tillbaka uppåt.
Det var väl lite genialt på sitt sätt, men fy tusan vad jobbig koden var. Funktionsrekursion är otroligt mycket enklare, vilket jag fick lära mig något år senare.
...undrar vad som hänt med CCW (Computer Club West)?
Känns inte som om Göteborg har samma underbara programmeringskult längre.

2007-09-20 @ 19:41:27
URL: http://blaufish.blogg.se/
Postat av: Kaprifol

Fisken, jag tycker att du söka upp dina gamla vänner från CCW och se hur det är med dem! Smart det där med att använda länkade listor, det blir väl lite som cons-celler som man använder i Lisp, antar jag.

2007-09-21 @ 07:06:49
URL: http://kaprifol.blogg.se
Postat av: Haffe

För att göra det hela ännu mer förvirrande så kan man dela in det hela ännu finar, det är nämnligen fullt möjligt att ha rekurssiva processer som arbetar itterativ och itterativa processer som arbetar rekursivt.

2007-09-22 @ 14:24:10

Kommentera inlägget här:

Namn:
Kom ihåg mig?

E-postadress:

URL:

Kommentar:

Trackback