Rekursion

Innehåll- 1. Rekursion - 2. Rekursion

1. Rekursion

"Se rekursion" -- Norsk ordbok

2. Rekursion

Rekursion är en teknik att lösa ett problem (eller definiera ett begrepp) genom att dela upp det på något systematiskt sätt i likartade, mindre problem (begrepp). Uppdelningen upprepas rekursivt till dess att de återstående problemens lösning (de återstående begreppens definition) är kända. Vid varje upprepning kontrolleras om lösningen (definitionen) är känd eller ej. Fallet att lösningen är känd kallas basfall, rekursionen avslutas och svaret från basfallet ges som delresultat. Fallet att lösningen ej är känd kallas rekursiva fallet, delproblemet delas upp eller förenklas igen och ett nytt försök görs att lösa det nya, mindre problemet. När all rekursion avslutats samlas delresultaten upp och kombineras i varje rekursivt steg tills hela problemet är löst.

För att tekniken eller definitionen ska kunna kallas rekursiv, så måste de mindre problemen (utom basfallen) lösas med samma teknik som huvudproblemet.

Inom datalogin är rekursion en viktig teknik för att konstruera algoritmer (ge struktur åt program). Andra sådana tekniker är sekvensen, selektionen och iterationen. I många fall kan samma problem lösas med hjälp av antingen rekursion eller iteration. Vad som är bäst beror av många faktorer, inte minst vilken teknik som har bäst stöd i den aktuella programmeringsmiljön.

Ett exempel är att operationen multiplikation av naturliga tal kan utföras rekursivt som mutiplikation av ett mindre tal (egentligen ett tal närmare noll) och operationerna addition och subtraktion av naturliga tal:

Multiplicera M med N:

Är M eller N lika med noll?

• Ja: resultatet är lika med noll, klart. (triviala fallet)
• Nej: Sätt resultatet till M, fortsätt.

Är N lika med ett?

• Ja: resultatet är klart. (basfallet, M * 1 = M) (det här steget är egentligen onödigt)
• Nej: resultatet är resultatet av att addera M till resultatet av att multiplicera M med [N subtraherat med ett]. (rekursiva fallet, M * N = M + M * [N - 1])

Alternativt kan detta uttryckas så här för heltal , 0*m = 0Basfall|n*0 = 0Basfalln * m = <|Om n>0, n*m = m + (n-1)*mRekursionsfall ` Om n<0, n*m = m + (n+1)*mRekursionsfall

Se även

• Rekursion
• Rekursionsfall
• Basfall
• Rekursiv fläta
• Svansrekursion
• Cirkeldefinition

Kommentarer:

Eller enklare (och med multiplikationstecken i stället för asterisk):

,om n=0, n×m = 0n×m = < om n<0, n×m = -((-n)×m) `om n>0, n×m = m + (n-1)×m

Jag vet inte om regeln är enklare, kortare kanske - dessutom lite jobbig om m=0 och n=jättestorttal //Pel

Båda sätten är opraktiska som metoder för att utföra en multiplikation. Däremot så kan de användas för att definiera multiplikation, och då är en enkel regel med få fall att föredra. Om du ska bevisa att metoden du fick lära dig i skolan alltid fungerar enligt definitionen så blir beviset enklare med en enkel definition. Dessutom så är väl syftet med en sådan här artikel att förklara vad rekursion är, och då är det mer pedagogiskt med ett exempel som är enkelt att förstå än med ett som är optimerat att utföra. –Christer Romson, 1 maj 2003

Jag tycker fortfarande att första exemplet är enklare. Du behöver som mest använda två av reglerna och du behöver inte bry dig om teckenändringar. Fast smaken är som baken... //Pel

Ska det vara enkelt är potensberäkning lättare att ta till sig än multiplikation. Potenser lär man sig i skolan som en upprepning av multiplikation. Dessutom beräknar man potenser med hjälp av multiplikation i huvudet. En multiplikation beräknas sällan som upprepad addering, ens då det ska göras som "huvudräkning". Exempel:

rekursiv_potens(bas, potens)Om potens = 1returnera basAnnarsbas = bas * rekursiv_potens(bas, potens - 1)returnera bas

Lägg märke till att exemplet endast fungerar för potenser > eller = 1. Och att det är extremt ineffektivt eftersom man för exempelvis 3^4 beräknar 3^2 2 gånger (3^2 * 3^2 = 3^4). Men det är ganska beskrivande.

Rekursiv programmering är snyggt men man måste veta vad man håller på med, det här är det bästa sättet att köra slut på en dators minne. Antag att du har en funktion som villkorligen anropar sig själv rekursivt där villkoret alltid uppfylls. Då kommer stacken där b.l.a. den anropande adressen sparas att växa i det oändliga och göra slut på minnet. Ännu värre är det om funktionen vid varje anrop allokerar ett antal variabler eller minnesblock, då kan det snabbt gå slut på minne även om funktionen slutar att anropa sig själv efter ett tag. // Solkoll

Redigera?

Artikeln skriven 2009-01-17 av Learning4sharing

Inga kategorier för denna artikel än...

Intresserad av fler artiklar?

Aido
Oracle
SICStus Prolog
Will Self
Extrem programmering
Objektorienterade programspråk
Mönstermatchning
Mönstermatchning
Super Mario