Rekursion
Spegel i spegeleffekt kallas drosteeffekten och är ett exempel på rekursion.
Rekursion uppstår när någonting definieras i termer av sig själv. Rekursion används inom en mängd olika discipliner, från lingvistik till logik. Det vanligaste användningsområdet av rekursion är inom matematik och datavetenskap, där en funktion definieras som tillämpad på sig själv. Även om detta tydligen definierar ett oändligt antal instanser (funktionsvärden), görs det ofta på ett sådant sätt att ingen slinga eller oändlig kedja av referenser kan förekomma.
Sammansatt ränta är exempel på ett rekursivt samband. Om Ak representerar värdet av en investering efter k år och den fasta räntan är r, kan sambandet mellan två konsekutiva år skrivas
- Ak=Ak−1+rAk−1=(1+r)Ak−1{displaystyle A_{k}=A_{k-1}+rA_{k-1}=(1+r)A_{k-1}}
Om A0 är det initiala värdet kan värdet efter tre år bestämmas som
- A3=(1+r)A2=(1+r)2A1=(1+r)3A0{displaystyle A_{3}=(1+r)A_{2}=(1+r)^{2}A_{1}=(1+r)^{3}A_{0}}
En rekursiv funktion som beräknar sammansatt ränta kan definieras enligt
- F(n):={A0om n=0basfall, sista anropet i anropskedjan(1 + r)⋅F(n − 1)om n > 0{displaystyle F(n):={begin{cases}A_{0}&{text{om}} n=0&{text{basfall, sista anropet i anropskedjan}}\(1 + r)cdot F(n - 1)&{text{om}} n > 0end{cases}}}
där n betecknar antalet år och r den fasta räntesatsen.
Innehåll
1 Exempel
2 Se även
3 Referenser
4 Externa länkar
Exempel |
- Ett klassiskt exempel på en rekursiv funktion är beräkningen av fibonaccital:
- F(n):={1om n=0basfall 11om n=1basfall 2F(n−1)+F(n−2)om n>1{displaystyle F(n):={begin{cases}1&{text{om}} n=0&{text{basfall 1}}\1&{text{om}} n=1&{text{basfall 2}}\F(n-1)+F(n-2)&{text{om}} n>1&\end{cases}}}
- F(n):={1om n=0basfall 11om n=1basfall 2F(n−1)+F(n−2)om n>1{displaystyle F(n):={begin{cases}1&{text{om}} n=0&{text{basfall 1}}\1&{text{om}} n=1&{text{basfall 2}}\F(n-1)+F(n-2)&{text{om}} n>1&\end{cases}}}
- Beräkning av fakultet, (n!):
- F(n):={1om n=0basfalln⋅F(n−1)om n>0{displaystyle F(n):={begin{cases}1&{text{om}} n=0&{text{basfall}}\ncdot F(n-1)&{text{om}} n>0&\end{cases}}}
- F(n):={1om n=0basfalln⋅F(n−1)om n>0{displaystyle F(n):={begin{cases}1&{text{om}} n=0&{text{basfall}}\ncdot F(n-1)&{text{om}} n>0&\end{cases}}}
- En subrutin i ett datorprogram som anropar sig själv, antingen direkt eller genom att anropa andra rutiner som till slut anropar den första igen.
- En domstol som dömer sig själv.
- En webbsida som via en länk refererar till sig själv. Denna länk är ett exempel.
Se även |
- Rekursiv funktion
- Rekursiv algoritm
- Rekursiv mängd
- Självreferens
- Generativ grammatik
Referenser |
Dijkstra, Edsger W. (1960). ”Recursive Programming”. Numerische Mathematik 2 (1): sid. 312–318. doi:.
Externa länkar |
Wikimedia Commons har media som rör Rekursion.Bilder & media
Wikimedia Commons har media som rör Rekursion.
