Rekursion

Innehåll- 1. Rekursion - 2. Rekursion

1. Rekursion

"Se rekursion" -- Norsk ordbok

2. Rekursion

Rekursion är en teknik att lösa ett besvär (eller definiera ett begrepp) genom att klyva opp det villig något systematiskt fason i likartade, mindre besvär (begrepp). Uppdelningen upprepas rekursivt mot dess att dom kvarvarande problemens solution (de kvarvarande begreppens definition) är kända. Vid varje eko kontrolleras försåvitt lösningen (definitionen) är berömd eller ej. Fallet att lösningen är berömd kallas basfall, rekursionen avslutas samt svaret från basfallet ges som delresultat. Fallet att lösningen ej är berömd kallas rekursiva fallet, delproblemet delas opp eller förenklas igen samt ett nytt ansats görs att lösa det nya, mindre problemet. När all rekursion avslutats hopas delresultaten opp samt kombineras i varje rekursivt kliv tills hela problemet är löst.

För att tekniken eller definitionen skall kunna kallas rekursiv, så plikt dom mindre problemen (utom basfallen) lösas med samma teknik som huvudproblemet.

Inom datalogin är rekursion en angelägen teknik för att konstruera algoritmer (ge anatomi åt program). Andra sådana tekniker är sekvensen, selektionen samt iterationen. I flertal baisse kan samma besvär lösas med assistans av antingen rekursion eller iteration. Va som är bäst beror av flertal faktorer, ej minst vilken teknik som har bäst support i den aktuella programmeringsmiljön.

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

Multiplicera M med N:

Är M eller N ekvivalent noll?

• Ja: resultatet är ekvivalent noll, färdigt. (triviala fallet)
• Nej: fason resultatet mot M, fortsätt.

Är N ekvivalent 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 mot 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 ` försåvitt 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 = < försåvitt n<0, n×m = -((-n)×m) `om n>0, n×m = m + (n-1)×m

Jag vet ej försåvitt regeln är enklare, kortare kanhända - dessutom lite ansträngande försåvitt m=0 samt n=jättestorttal //Pel

Båda sätten är opraktiska som metoder för att förrätta en multiplikation. Däremot så kan dom användas för att definiera multiplikation, samt då är en enkel bestämmelse med erhålla baisse att föredra. Försåvitt du skall bevisa att metoden du fick doktrin dig i plugget förgott funkar 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örtydliga va rekursion är, samt då är det mer pedagogiskt med ett föredöme som är lätt att begripa än med ett som är optimerat att utföra. –Christer Romson, 1 maj 2003

Jag anser ännu att första exemplet är enklare. Du behöver som mest begagna par av reglerna samt du behöver ej bry dig försåvitt teckenändringar. Orubblig smaken är som baken... //Pel

Ska det produkt lätt är potensberäkning lättare att gripa mot sig än multiplikation. Potenser lär man sig i plugget som en eko av multiplikation. Dessutom beräknar man potenser med assistans av multiplikation i huvudet. En multiplikation beräknas sällan som upprepad addering, ens då det skall göras som "huvudräkning". Exempel:

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

Lägg emblem mot att exemplet bara funkar för potenser > eller = 1. Samt att det är oerhört ineffektivt eftersom man för exempelvis 3^4 beräknar 3^2 2 gånger (3^2 * 3^2 = 3^4). Skada det är ganska deskriptiv.

Rekursiv programmering är snyggt skada man plikt veta va man håller villig med, det här är det bästa sättet att kugga tillända villig en dators minne. Antag att du har en funktion som villkorligen anropar sig själv rekursivt där villkoret förgott uppfylls. Då kommer stacken där b.l.a. Den anropande adressen sparas att expandera i det oändliga samt förinta minnet. Ännu värre är det försåvitt funktionen vid varje anrop allokerar ett mängd variabler eller minnesblock, då kan det fartfyllt knalla tillända villig minne även försåvitt funktionen avgår att anropa sig själv efter ett grepp. // 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